AC0

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

AC0 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 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 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(+, \times), 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).

Literatur[Bearbeiten]

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

Weblinks[Bearbeiten]

  • AC0. In: Complexity Zoo. (englisch)

Einzelnachweise[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. 17, 1984, S. 13–27 (online).
  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 (PDF, online).