AC0

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

AC0 ist eine Komplexitätsklasse in der Schaltkreiskomplexität, einem Teilgebiet der Komplexitätstheorie. Sie enthält alle Funktionen, die von Schaltkreisfamilien mit Tiefe 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 NC0, das nur Gatter mit beschränktem Fan-In erlaubt.

In der deskriptiven Komplexitätstheorie entspricht DLOGTIME-uniformes AC0 der deskriptiven Klasse FO+BIT der Sprachen, die in Logik erster Stufe mit dem BIT-Operator beschrieben werden können, der Klasse FO(+, ), und der logarithmischen Hierarchie.[1]

1984 zeigten Furst, Saxe und Sipser, dass die Parity-Funktion nicht in AC0 liegt.[2][3] Daraus folgt, dass auch die Majority-Funktion nicht in AC0 liegt. Daraus folgt, dass AC0 ungleich NC1 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 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 -Gatter mit Eingängen ist das Output genau dann Null, falls die Anzahl der Einsen in den Inputs ein Vielfaches von ist. Für ergibt sich das XOR-Gatter.

  • AC0. In: Complexity Zoo. (englisch)

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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]).