„AC0" – Versionsunterschied

AC⁰ ist eine Komplexitätsklasse in der Schaltkreiskomplexität, einem Teilgebiet der Komplexitätstheorie. Sie enthält alle Funktionen, die von Schaltkreisfamilien mit Tiefe ${\displaystyle O(1)}${\displaystyle O(1)} und polynomieller Größe mit Und-Gattern/Oder-Gattern mit unbeschränktem Fan-In, und eventuell Nicht-Gattern an den Eingängen berechnet werden können. Sie ist die kleinste Klasse in der AC-Hierarchie und liegt über NC⁰, das nur Gatter mit beschränktem Fan-In erlaubt.

In der deskriptiven Komplexitätstheorie entspricht DLOGTIME-uniformes AC⁰ der deskriptiven Klasse FO+BIT der Sprachen, die in Logik erster Stufe mit dem BIT-Operator beschrieben werden können, der Klasse FO(+, ${\displaystyle \times }${\displaystyle \times }), und der logarithmischen Hierarchie.^[1]

1984 zeigten Furst, Saxe und Sipser, dass die Parity-Funktion nicht in AC⁰ liegt.^{[2] [3]} Daraus folgt, dass auch die Majority-Funktion nicht in AC⁰ liegt. Daraus folgt, dass AC⁰ ungleich NC¹ ist. Addition und Subtraktion ganzer Zahlen liegen in AC⁰, Multiplikation dagegen nicht (zumindest mit den gewöhnlichen Darstellungen zur Basis 2 oder 10).

Nimmt man zusätzlich zu AND, OR, NOT allgemeine modulare Gatter hinzu, hat man die Komplexitätsklasse ACC0. Dabei sind Mod-Gatter (modulare Gatter) Verallgemeinerungen von XOR-Gattern: Bei einem ${\displaystyle \mod m}${\displaystyle \mod m}-Gatter mit ${\displaystyle n}${\displaystyle n} Eingängen ist das Output genau dann Null, falls die Anzahl der Einsen in den Inputs ein Vielfaches von ${\displaystyle m}${\displaystyle m} ist. Für ${\displaystyle m=2}${\displaystyle m=2} ergibt sich das XOR-Gatter.

• Stasys Jukna: Boolean function complexity. Advances and frontiers. Springer, 2012, ISBN 978-3-642-24507-7. 

• AC0. In: Complexity Zoo. (englisch)

1. ↑ Neil Immerman: Descriptive complexity. Springer, 1999, S. 85. 
2. ↑ M. Furst, J. B. Saxe und M. Sipser: Parity, circuits, and the polynomial-time hierarchy. In: Mathematical Systems Theory. Band 17, 1984, S. 13–27, doi:10.1007/BF01744431 . 
3. ↑ Johan Håstad: Almost Optimal Lower Bounds for Small Depth Circuits. In: Silvio Micali (Hrsg.): Randomness and Computation. JAI Press, 1989, ISBN 0-89232-896-7, S. 6–20 (online (Memento vom 22. Februar 2012 im Internet Archive ) [PDF; abgerufen am 24. September 2012]). 

• Komplexitätsklasse