논리 회로(회로 복잡도)

입력 비트에서 출발해 AND, OR, NOT 게이트를 차례로 거쳐 출력 비트를 내는 계산 모형이다. 게이트 수를 크기, 입력에서 출력까지 가장 긴 경로를 깊이라 한다. 다항 시간 알고리즘은 다항 크기의 회로로 옮길 수 있으므로, NP 문제에 다항 크기 회로가 없음을 보이면 P ≠ NP 다. 회로는 유한한 조합 구조여서 튜링 기계보다 분석하기 쉬우리라는 기대로 1980년대에 활발히 연구되었다. 대부분의 함수는 지수 크기의 회로가 필요하다는 것이 개수 세기로 알려져 있지만(섀넌, 1949), NP 의 구체적인 문제에 대해 증명된 일반 회로 하한은 입력 수의 상수 배 수준에 머물러 있다.