최소 회로 크기 문제(MCSP)

함수의 진리표 전체와 수 s 가 주어질 때, 그 함수를 계산하는 크기 s 이하의 회로가 있는지 묻는다. 회로를 증거로 삼으면 되므로 NP 에 속하지만, P 에 속하는지도 NP-완전인지도 알려져 있지 않다. 카바네츠(Kabanets)와 차이(Cai)는 2000년에 이 문제가 자연 증명과 맞닿아 있음을 밝혔다. MCSP 가 쉽다면 강한 유사난수 생성기가 존재할 수 없고, 흔한 방식으로 NP-완전임을 증명하면 그것만으로 새로운 회로 하한이 따라 나온다. 「문제의 어려움을 판정하는 문제의 어려움」을 다루는 메타 복잡도 연구의 중심 문제다.