AC0

Diagramm eines AC0 Schaltung: Die N -Eingangsbits befinden sich unten und das obere Tor erzeugt den Ausgang. Der Schaltkreis besteht aus und aus und or-Gates des polynomialen Lüfters, und die Wechseltiefe wird durch eine Konstante begrenzt.

AC0 ist ein Komplexitätsklasse benutzt in Komplexität der Schaltung. Es ist die kleinste Klasse in der AC Hierarchie und besteht aus allen Familien von Schaltkreisen der Tiefe o (1) und der Polynomgröße mit unbegrenztem-Fanin Und Tore und Oder Tore (wir erlauben Keine Tore Nur bei den Eingängen).[1] Es enthält also NC0, das nur begrenztes Fanin und und und Tore.[1]

Beispielprobleme

Ganzzahl Addition und Subtraktion sind in AC berechnetbar0,[2] Die Multiplikation ist jedoch nicht (zumindest nicht unter der üblichen Binärdatei[3] oder Basis-10-Darstellungen von Ganzzahlen).

Da es sich um eine Schaltungsklasse handelt, wie P/poly, Ac0 Enthält auch alle Unary Sprache.

Beschreibende Komplexität

Von einem Beschreibende Komplexität Standpunkt, Dlogime-Uniform AC0 ist gleich der beschreibenden Klasse Fo+Bit von allen Sprachen Beschreibbar in Logik erster Ordnung mit Zugabe der Bit Prädikatoder alternativ durch fo (+, ×) oder durch Turing Maschine in dem logarithmische Hierarchie.[4]

Trennungen

1984 Furst, Saxe und SIPser zeigte, dass die Berechnung des Parität einer Eingabe kann von keinem AC entschieden werden0 Schaltkreise, sogar mit Ungleichmäßigkeit.[5][1] Daraus folgt, dass AC0 ist ungleich zu NC1, weil eine Familie von Schaltungen in der letzteren Klasse die Parität berechnen kann.[1] Genauere Grenzen folgen aus Lemma wechseln. Mit ihnen wurde gezeigt, dass es eine Orakel -Trennung zwischen dem gibt Polynomhierarchie und PSPACE.

Verweise

  1. ^ a b c d Arora, Sanjeev; Barak, Boaz (2009). Rechenkomplexität. Ein moderner Ansatz. Cambridge University Press. pp.117–118, 287. ISBN 978-0-521-42426-4. Zbl 1193.68112.
  2. ^ Barrington, David Mix; Maciel, Alexis (18. Juli 2000). "Vortrag 2: Die Komplexität einiger Probleme" (PDF). IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate -Programm: Grundkurs zur Computerkomplexität.
  3. ^ Kayal, Neeraj; Hegde, Sumant (2015). "Vortrag 5: 4. Februar 2015" (PDF). E0 309: Themen in der Komplexitätstheorie. Archiviert (PDF) vom Original am 2021-10-16. Abgerufen 2021-10-16.
  4. ^ Immerman, N. (1999). Beschreibende Komplexität. Springer. p.85.
  5. ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parität, Schaltungen und die Polynom-Zeit-Hierarchie". Theorie der mathematischen Systeme. 17 (1): 13–27. doi:10.1007/bf01744431. HERR 0738749. Zbl 0534.94008.