imported>MaaaxiKing: Formatierung/Darstellung, Fix

2024-05-26T13:53:39Z

Formatierung/Darstellung, Fix

Neue Seite

{{SEITENTITEL:AC0}}
'''AC0''' ist eine [[Komplexitätsklasse]] in der [[Schaltkreiskomplexität]], einem Teilgebiet der [[Komplexitätstheorie]].
Sie enthält alle Funktionen, die von [[Logikfamilie|Schaltkreisfamilien]] mit Tiefe <math>O(1)</math> und polynomieller Größe mit [[Und-Gatter]]n/[[Oder-Gatter]]n mit unbeschränktem [[Fan-In]], und eventuell [[Nicht-Gatter]]n an den Eingängen berechnet werden können. Sie ist die kleinste Klasse in der [[AC (Komplexitätsklasse)|AC]]-Hierarchie und liegt über [[NC0|NC0]], das nur Gatter mit beschränktem Fan-In erlaubt.

In der [[Deskriptive Komplexitätstheorie|deskriptiven Komplexitätstheorie]] entspricht [[DLOGTIME]]-[[uniform]]es AC0 der deskriptiven Klasse [[FO (Komplexitätsklasse)|FO]]+BIT der Sprachen, die in [[Logik erster Stufe]] mit dem [[BIT-Operator]] beschrieben werden können, der Klasse FO(+, <math>\times</math>), und der [[Logarithmische Hierarchie|logarithmischen Hierarchie]].<ref>{{Literatur |Autor=[[Neil Immerman]] |Titel=Descriptive complexity |Verlag=Springer |Datum=1999 |Seiten=85}}</ref>

1984 zeigten Furst, Saxe und Sipser, dass die [[Parity]]-Funktion nicht in AC0 liegt.<ref>{{Literatur |Autor=M. Furst, J. B. Saxe und M. Sipser |Titel=Parity, circuits, and the polynomial-time hierarchy |Sammelwerk=Mathematical Systems Theory |Band=17 |Datum=1984 |Seiten=13–27 |DOI=10.1007/BF01744431}}</ref><ref>{{Literatur |Autor=[[Johan Håstad]] |Hrsg=[[Silvio Micali]] |Titel=Almost Optimal Lower Bounds for Small Depth Circuits |Sammelwerk=Randomness and Computation |Verlag=JAI Press |Datum=1989 |ISBN=0-89232-896-7 |Seiten=6–20 |Online={{Webarchiv | url=http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf | wayback=20120222163102 | text=online}} |Abruf=2012-09-24 }}</ref> Daraus folgt, dass auch die [[Majority]]-Funktion nicht in AC0 liegt. Daraus folgt, dass AC0 ungleich [[NC1|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 <math>\mod m</math>-Gatter mit <math>n</math> Eingängen ist das Output genau dann Null, falls die Anzahl der Einsen in den Inputs ein Vielfaches von <math>m</math> ist. Für <math>m=2</math> ergibt sich das XOR-Gatter.

== Literatur ==
* {{Literatur |Autor=Stasys Jukna |Titel=Boolean function complexity. Advances and frontiers |Verlag=Springer |Datum=2012 |ISBN=978-3-642-24507-7}}

== Weblinks ==
* {{Complexity Zoo|AC0|A#ac0}}

== Einzelnachweise ==
<references />

[[Kategorie:Komplexitätsklasse]]

AC0 - Versionsgeschichte

imported>MaaaxiKing: Formatierung/Darstellung, Fix