AC⁰

입력을 몇 개든 받는 AND·OR 게이트와 NOT 을 쓰되 깊이는 상수, 크기는 다항식 이하인 회로족이 계산하는 문제의 모임이다. 덧셈은 AC⁰ 에 속하지만, 입력에서 1 의 개수가 홀수인지 묻는 패리티 함수는 속하지 않는다. 이는 Furst·Saxe·Sipser(1981)와 Ajtai(1983)가 증명했고, Håstad(1986)가 지수에 가까운 하한으로 다듬었다. 구체적인 함수에 대해 강한 하한을 증명한 드문 성공 사례이지만, 쓰인 방법은 자연 증명 장벽에 걸려 더 강한 회로 종류로는 그대로 넓혀지지 않는다.