AC0

AC0 ist eine Komplexitätsklasse in der , einem Teilgebiet der Komplexitätstheorie.Sie enthält alle Funktionen, die von Schaltkreisfamilien mit Tiefe O(1) und polynomieller Größe mit Und-Gattern und 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 , das nur Gatter mit beschränktem Fan-In erlaubt. In der deskriptiven Komplexitätstheorie entspricht -uniformes AC0 der deskriptiven Klasse +BIT der Sprachen, die in Logik erster Stufe mit dem beschrieben werden können, der Klasse FO(+, ), und der . 1984 zeigten Furst, Saxe und Sipser, dass die Parity-Funktion nicht in AC0 liegt. Daraus folgt, dass auch die -Funktion nicht in AC0 liegt. Daraus folgt, dass AC0 ungleich ist. Addition und Subtraktion ganzer Zahlen liegen in AC0, Multiplikation dagegen nicht (zumindest mit den gewöhnlichen Darstellungen zur Basis 2 oder 10). Nimmt man zusätzlich zu UND, AND, NOT Gattern 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).