AC0
# AC0

AC$^0$ ist eine Komplexitätsklasse in der Schaltkreiskomplexität, einem Teilgebiet der Komplexitätstheorie. Sie enthält alle Funktionen, die von Schaltkreisfamilien mit Tiefe $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$^0$, das nur Gatter mit beschränktem Fan-In erlaubt.
In der deskriptiven Komplexitätstheorie entspricht DLOGTIME-uniformes AC$^0$ der deskriptiven Klasse FO+BIT der Sprachen, die in Logik erster Stufe mit dem BIT-Operator beschrieben werden können, der Klasse FO(+, $\times$), und der logarithmischen Hierarchie.
1984 zeigten Furst, Saxe und Sipser, dass die Parity-Funktion nicht in AC$^0$ liegt. Daraus folgt, dass auch die Majority-Funktion nicht in AC$^0$ liegt. Daraus folgt, dass AC$^0$ ungleich NC$^1$ ist. Addition und Subtraktion ganzer Zahlen liegen in AC$^0$, 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 $\mod m$-Gatter mit $n$ Eingängen ist das Output genau dann Null, falls die Anzahl der Einsen in den Inputs ein Vielfaches von $m$ ist. Für $m=2$ ergibt sich das XOR-Gatter.