P/poly

입력 길이 n 마다 크기가 n 의 다항식 이하인 논리 회로가 하나씩 있어 그 길이의 입력을 모두 옳게 판정하는 결정 문제의 모임이다. 길이마다 다른 회로를 쓰고 그 회로를 어떻게 얻는지는 따지지 않으므로 「비균일」 모형이라 한다. P ⊆ P/poly 이고 BPP ⊆ P/poly 이며, 알고리즘으로는 풀 수 없는 문제도 일부 들어 있다. NP 의 어떤 문제가 P/poly 에 속하지 않음을 보이면 P ≠ NP 가 증명되므로, 이것이 회로 하한 접근의 목표다. NP ⊆ P/poly 이면 다항 위계가 둘째 층으로 무너진다(카프–립턴 정리).