AC0

AC⁰(교대 회로, 영어: alternating circuit)는 회로 복잡도에서 사용되는 복잡도 종류이다. AC⁰는 AC 위계에서 가장 작은 종류로, 깊이가 O(1)이고 크기가 다항식인 회로군으로 구성된다. 이때 AND 게이트와 OR 게이트의 팬인은 제한이 없다(단, NOT 게이트는 입력단에서만 허용된다). 따라서 AC⁰는 제한된 팬인의 AND 및 OR 게이트만을 허용하는 NC⁰을 포함한다. 이러한 회로를 "교대 회로"라고 부르는데, 이는 층이 AND와 OR 사이를 번갈아 가며 구성될 필요가 있기 때문이다. AND 뒤에 AND가 오는 것은 하나의 AND와 같고, OR의 경우도 마찬가지이기 때문이다.

예시 문제

정수의 덧셈과 뺄셈은 AC⁰에서 계산 가능하다. 하지만 곱셈은 그렇지 않다(구체적으로, 입력이 통상적인 이진법이나 10진법으로 표현된 두 정수일 경우).

회로 종류인 P/poly와 마찬가지로, AC⁰ 역시 모든 단항 언어를 포함한다.

기술적 복잡도

기술적 복잡도(descriptive complexity) 관점에서, DLOGTIME-균일 AC⁰는 BIT 술어가 추가된 1차 논리(first-order logic)로 기술할 수 있는 모든 형식 언어의 기술적 종류인 FO+BIT와 동일하다. 이는 대안적으로 FO(+, ×)로 표현하거나, 로그 계층에 있는 튜링 기계로 표현할 수도 있다.

분리

1984년 퍼스트(Furst), 색스(Saxe), 그리고 십서는 입력 비트의 패리티(PARITY)를 계산하는 문제가(앞서 언급한 덧셈/뺄셈 문제와는 달리) 비균일성을 고려하더라도 어떤 AC⁰ 회로로도 결정할 수 없음을 보였다. 마찬가지로, 다수결(majority) 계산 또한 ${\displaystyle {\mathsf {AC}}^{0}}$에 속하지 않는다. 이로부터 AC⁰는 TC⁰보다 엄격하게 작다는 결론이 도출된다. 참고로 "패리티"는 문헌에서 "XOR"이라고 불린다.

하지만 패리티는 AC⁰에서 아주 조금 벗어나 있을 뿐인데, 임의의 ${\displaystyle k>0}$에 대하여 깊이 ${\displaystyle \lceil k\ln n/\ln \ln n\rceil }$와 크기 ${\displaystyle O\left(2^{(\ln n)^{1/k}}{\frac {n}{(\ln n)^{1/k}}}\right)}$를 사용하는 교대 회로군이 존재하기 때문이다.^: 135 특히 ${\displaystyle k}$를 큰 상수로 설정하면, 깊이 ${\displaystyle O(\ln n/\ln \ln n)\ll O(\ln n)}$이고 크기가 초선형(superlinear)인 교대 회로군이 존재한다.

${\displaystyle {\mathsf {AC}}^{0}}$는 더 세분화되어 1계층, 2계층 등을 요구하는 언어의 위계로 나뉠 수 있다. ${\displaystyle {\mathsf {AC}}_{d}^{0}}$를 최대 깊이 ${\displaystyle d}$인 임계 회로군(threshold circuit family)으로 결정 가능한 언어의 종류라고 하자:$${\displaystyle {\mathsf {AC}}_{1}^{0}\subset {\mathsf {AC}}_{2}^{0}\subset \cdots \subset {\mathsf {AC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {AC}}_{d}^{0}}$$다음 문제는 균일성 조건 하에서 ${\displaystyle {\mathsf {AC}}_{d}^{0}}$-완전이다: 다항식 길이와 폭 ${\displaystyle d}$를 가진 격자 그래프가 주어졌을 때, 주어진 두 정점이 연결되어 있는지 결정하라.

두 ${\displaystyle n}$비트 정수의 덧셈은 ${\displaystyle {\mathsf {AC}}_{3}^{0}}$에는 속하지만 ${\displaystyle {\mathsf {AC}}_{2}^{0}}$에는 속하지 않는다.^: 148

각주