정의
비공식적으로, ACC0는 상수 깊이와 다항 크기를 갖는 불리언 회로로 실현되는 계산 종류를 모델링하며, 이때 회로 게이트에는 고정된 상수 모듈로 입력 중 참인 값의 개수를 계산하는 "모듈러 계수 게이트(modular counting gates)"가 포함된다.
더 공식적으로, 언어 L이 AC0[m]에 속한다는 것은 L이 회로군 C1, C2, ...에 의해 계산될 수 있음을 의미한다. 여기서 Cn은 n개의 입력을 받고, 모든 회로의 깊이는 상수이며, Cn의 크기는 n의 다항 함수이고, 회로는 다음의 게이트들을 사용한다: 입력의 논리곱과 논리합을 계산하는 무제한 팬 인(unbounded fan-in)의 AND 게이트 및 OR 게이트; 단일 입력의 부정을 계산하는 NOT 게이트; 그리고 입력 중 1의 개수가 m의 배수이면 1을 출력하는 무제한 팬 인의 MOD-m 게이트. 어떤 m에 대해 언어가 AC0[m]에 속하면, 그 언어는 ACC0에 속한다.
일부 문헌에서 ACCi는 ACC0를 최하위 수준으로 하는 회로 클래스의 계층을 지칭하며, ACCi의 회로는 O(login)의 깊이와 다항 크기를 가진다.
ACC0 종류는 모노이드 상의 비균일 결정론적 유한 오토마타(NUDFA)의 계산으로도 정의될 수 있다. 이 체계에서 입력은 고정된 모노이드의 원소로 해석되며, 입력 원소들의 곱이 주어진 모노이드 원소 목록에 속하면 입력이 허용된다. ACC0 종류는 가해군을 부분 반군(subsemigroup)으로 포함하지 않는 임의의 모노이드에 대한 NUDFA에 의해 허용되는 언어들의 집합이다.
계산 능력
ACC0 종류는 AC0를 포함한다. 이 포함 관계는 진부분집합 관계인데, 단일 MOD-2 게이트는 패리티 함수를 계산하며 이는 AC0에서 계산할 수 없음이 알려져 있기 때문이다. 더 일반적으로, m이 p의 거듭제곱이 아닌 경우 MODm 함수는 소수 p에 대해 AC0[p]에서 계산될 수 없다.
ACC0 종류는 TC0에 포함된다. ACC0가 입력의 다수결 함수를 계산할 수 없다는(즉, TC0로의 포함 관계가 진부분집합이라는) 추측이 있지만, 2018년 7월 기준으로 아직 해결되지 않았다.
ACC0의 모든 문제는 깊이 2인 회로로 해결될 수 있으며, 이 회로는 입력단에 다항로그(polylogarithmic) 팬 인을 갖는 AND 게이트들이 있고, 이들이 입력의 순서에 의존하지 않는 대칭 함수를 계산하는 단일 게이트에 연결된 형태이다. 이러한 회로를 SYM+-회로라 부른다. 이 증명은 토다의 정리 증명 아이디어를 따른다.
Williams (2011)은 ACC0가 NEXPTIME을 포함하지 않음을 증명한다. 이 증명은 시간 계층 정리, IP = PSPACE, 비랜덤화(derandomization), 그리고 SYM+ 회로를 통한 ACC0의 표현 등 복잡도 이론의 많은 결과를 사용한다. Murray & Williams (2018)은 이 하한을 개선하여 ACC0가 NQP(비결정론적 준다항시간)를 포함하지 않음을 증명하였다.
영구식 계산(computing the permanent)은 LOGTIME-균일 ACC0 회로로는 불가능함이 알려져 있으며, 이는 복잡도 종류 PP가 LOGTIME-균일 ACC0에 포함되지 않음을 의미한다.
