AC(복잡성)

회로 복잡성에서 AC는 복잡도 등급 계층이다.각 클래스 AC는ⁱ 깊이 $O{\displaystyle ({\log }^{}}$ ${\displaystyle i^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle$ O$(\log ^{i}n)$를 가진 부울 회로가 인식하는 언어와 무제한 팬인 AND 및 OR 게이트의 다항식 번호로 구성된다.null

"AC"라는 명칭은 NC와 유사하게 선택되었으며, 이름에 "A"는 "교체"를 의미하며, 회로에서 AND와 OR 게이트 사이의 교대 및 튜링 기계를 교대하는 것을 가리킨다.^[1]null

가장 작은 AC 클래스는 AC로⁰, 일정한 깊이의 무제한 팬인 회로로 구성된다.null

AC 클래스의 총 계층은 다음과 같이 정의된다.

${\displaystyle {\mbox}AC}}=\빅컵 _{i\geq 0}{\mbox{AC}^{i}}}$

NC와의 관계

AC 클래스는 NC 클래스와 유사하게 정의되지만 게이트는 일정한 팬인만 가지고 있다.나 한 명당, 우리는^[2][3]

${\displaystyle {\mbox}NC}^{i}\subseteq{\mbox{AC}^{i}\subseteq {\mbox{NC}^{i+1}.}$

이것의 즉각적인 결과로, 우리는 NC = AC를 가지게 되었다.^[4]null

i = 0에 대해서는 포함이 엄격한 것으로 알려져 있다.^[3]

변형

AC 클래스의 힘은 게이트를 추가함으로써 영향을 받을 수 있다.일부 계량 m에 대한 modulo 연산 계산 게이트를 추가하면 ACCⁱ[m] 클래스가 있다.^[4]null

메모들

참조

• Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Clote, Peter; Kranakis, Evangelos (2002), Boolean functions and computation models, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, ISBN 3-540-59436-1, Zbl 1016.94046
• Regan, Kenneth W. (1999), "Complexity classes", Algorithms and Theory of Computation Handbook, CRC Press.
• Vollmer, Heribert (1998), Introduction to circuit complexity. A uniform approach, Texts in Theoretical Computer Science, Berlin: Springer-Verlag, ISBN 3-540-64310-9, Zbl 0931.68055