In der Komplexitätstheorie ist AC 0 eine Komplexitätsklasse, die durch Boolesche Schaltkreise konstanter Tiefe definiert wird . Es ist Teil der AC-Hierarchie . Die Klasse AC 0 enthält die Addition, aber nicht die Paritätsfunktion, die Multiplikation oder das Primalitätsprädikat (siehe unten).
Die Klasse AC 0 ist die Komplexitätsklasse von Problemen bestimmt durch boolean Schaltungen konstante Tiefe, Polynom Größe, sind die Tore AND und OR , Grad incoming unbegrenzt (in der Tat andere Türen wie „erlaubt werden können , Exklusiv - ODER “ oder NOT - Gatter , weil sie ausdrückbar, ohne die Komplexität zu ändern, durch UND und ODER ). Das Akronym AC kommt von Alternation Circuit . Es ist Teil der AC-Hierarchie .
Die Addition ist in AC 0 . Genauer gesagt, für alle i ist das Entscheidungsproblem, das 2n Bits als Eingabe verwendet, die zwei Zahlen a und b von n Bits darstellen, und das das i- te Bit der Summe von a und b berechnet, in AC 0 .
Details zu einer Schaltung polynomialer Größe und konstanter Tiefe für die AdditionHier ist eine Möglichkeit, eine Schaltung aufzubauen, um das i- te Bit der Summe von a n-1 ... a 0 und b n-1 ... b 0 zu berechnen . Beachten Sie die ∧ "und"-Logik, ∨ das logische "oder" und ⊕ exklusives oder. Wir betrachten a j als einen Satz, wahr, wenn das j- te Bit von a gleich 1 ist, andernfalls falsch. Ebenso gilt b j als Aussage, wahr, wenn das j- te Bit von b gleich 1 ist, andernfalls falsch. Ebenso bezeichnen wir mit s j einen Satz, wahr, wenn das j- te Bit von s 1 ist, andernfalls falsch. Wir stellen auch andere Vorschläge vor:
Wir haben :
Die Anzahl der Gatter in der Schaltung, die den obigen Formeln entspricht, ist polynomiell in n. Außerdem ist die Tiefe der Schaltung konstant, wie die Schaltung in der obigen Abbildung zeigt.
Ebenso ist die Subtraktion in AC 0 .
Die Paritätsfunktion ist ein Prädikat, das 1 zurückgibt, wenn in der Eingabe die Anzahl der Bits 1 gerade ist, andernfalls 0 zurückgibt. In den 1970er Jahren , es war nicht bekannt, ob es AC 0- Kreise für das Cliquenproblem oder das Handlungsreisendeproblem gab . Tatsächlich haben Furst, Saxe und Sipser und unabhängig voneinander Miklós Ajtai gezeigt, dass dies nicht der Fall ist. Sie zeigten sogar, dass ein viel einfacheres Prädikat, nämlich die Paritätsfunktion , nicht zu AC 0 gehört . Johan Håstad zeigte dann ein stärkeres Ergebnis, das Switching Lemma (in) . Da sich die Paritätsfunktion in NC 1 befindet , folgern wir, dass die Einbeziehung von AC 0 in NC 1 strikt ist.
Die Majoritätsfunktion nimmt n Bits als Eingabe und gibt 1 zurück, wenn strikt mehr als die Hälfte der Bits gleich 1 sind. Diese Funktion befindet sich nicht in AC 0 . Wir können dies absurderweise demonstrieren, wenn die Mehrheit in AC 0 ist , indem wir zusätzliche Bits hinzufügen, können wir testen, ob x ≥ k ist , wobei x die ganze Zahl ist, die durch die fraglichen Bits repräsentiert wird und k eine Konstante ist; von dort können wir testen, ob x = k ; und teste daher die Parität , während du in AC 0 bist , was ein Widerspruch ist.
Die Multiplikation ist nicht in AC 0 und wird durch Reduktion aus der Paritätsfunktion gezeigt. Andererseits ist es in NC 1 .
Das Primalitätsprädikat , das testet, ob eine ganze Zahl eine Primzahl ist, befindet sich nicht in AC 0 .
Klasse AC 0 bezieht sich in der beschreibenden Komplexität auf die Logik erster Ordnung .