단조 회로

NOT 게이트를 쓰지 않는 논리 회로다. 입력의 0 을 1 로 바꿨을 때 출력이 1 에서 0 으로 떨어지지 않는 함수(단조 함수)만 계산할 수 있으며, 클릭 문제가 그런 함수다. 라즈보로프는 1985년에 클릭을 계산하는 단조 회로가 다항 크기일 수 없음을 증명했고, 이 하한은 곧 지수 꼴로 강화되었다. 그러나 다항 시간에 풀리는 문제 가운데에도 단조 회로로는 다항 크기에 풀리지 않는 것이 있음이 밝혀져, 단조 회로 하한이 일반 회로 하한(곧 P ≠ NP)으로 그대로 이어지지는 않는다.