ACC0
Acc0, manchmal genannt Acc, ist eine Klasse von Rechenmodellen und Problemen, die in definiert werden Komplexität der Schaltung, ein Feld der theoretischen Informatik. Die Klasse wird definiert, indem die Klasse erweitert wird AC0 von konstanten Tiefen "Wechselkreisläufen" mit der Fähigkeit zu zählen; Das Akronym ACC steht für "AC With Counters".[1] Insbesondere gehört ein Problem zu ACC0 Wenn es durch Polynomgrößen, konstante Tiefenschaltungen unbegrenzter Lüftertore gelöst werden kann, einschließlich Gates, die Modulo eine feste Ganzzahl zählen. Acc0 entspricht der Berechnung in einem lösbaren Monoid. Die Klasse ist in der theoretischen Informatik aufgrund der algebraischen Verbindungen sehr gut untersucht und da sie eines der größten konkreten Rechenmodelle ist, für die rechnerische Unmöglichkeitenergebnisse, sogenannte Schaltkreise untere Grenzen, nachgewiesen werden können.
Definitionen
Informell, ACC0 modelliert die Klasse der Berechnungen, die durch boolesche Schaltungen mit konstanter Tiefe und Polynomgröße realisiert werden, wobei die Schaltungsstore "modulare Zähltore" enthalten, die die Anzahl der echten Eingänge berechnen, die eine feste Konstante modulo modulo.
Formell wird eine Sprache zu AC gehört0[m] Wenn es von einer Familie von Schaltungen berechnet werden kann C1, C2, ..., wo Cn nimmt n Eingänge, die Tiefe jeder Schaltung ist konstant, die Größe von Cn ist eine Polynomfunktion von nund die Schaltung verwendet die folgenden Tore: Und Tore und Oder Tore von ungerätem Fan-inBerechnung der Konjunktion und Disjunktion ihrer Eingaben; Keine Tore Berechnung der Negation ihrer einzelnen Eingabe; und unbegrenzter Fan-in-Mod-m Gates, die 1 berechnen, wenn die Anzahl der Eingaben 1s ein Vielfaches von ist m. Eine Sprache gehört zu ACC0 Wenn es zu AC gehört0[m] für einige m.
In einigen Texten ACCi bezieht sich auf eine Hierarchie von Schaltungsklassen mit ACC0 auf seiner niedrigsten Ebene, wo die Schaltungen in ACCi Tiefe haben O(Protokollin) und Polynomgröße.[1]
Die Klasse ACC0 kann auch in Bezug auf Berechnungen von ungleichmäßigen deterministischen endlichen Automata (Nudfa) definiert werden Monoide. In diesem Framework wird die Eingabe als Elemente aus einem festen Monoid interpretiert, und der Eingang wird akzeptiert, wenn das Produkt der Eingabeelemente zu einer bestimmten Liste von Monoidelementen gehört. Die Klasse ACC0 Ist die Familie der Sprachen, die von einem Nudfa über einen Monoid akzeptiert werden, das keine enthält Unlösbare Gruppe als Subsemigroup.[2]
Rechenleistung
Die Klasse ACC0 inklusive AC0. Diese Aufnahme ist streng, da ein einzelnes Mod-2-Gate die Paritätsfunktion berechnet, von der bekannt ist0. Allgemeiner ist der Funktionsmodm kann nicht in AC berechnet werden0[p] für Prime p wenn nicht m ist eine Kraft von p.[3]
Die Klasse ACC0 ist enthalten in TC0. Es wird vermutet, dass ACC0 kann das nicht berechnen Mehrheitsfunktion seiner Eingänge (d. H. Die Aufnahme in TC0 ist streng), aber dies bleibt ab Juli 2018 ungelöst.
Jedes Problem in ACC0 Kann durch Schaltkreise von Tiefe 2 mit und Toren des Polylogarithmischen Lüfters an den Eingängen gelöst werden, die an eine einzelne Gate angeschlossen sind, die eine symmetrische Funktion berechnet.[4] Diese Schaltungen werden Symbol genannt+-Cirts. Der Beweis folgt den Ideen des Beweises von Todas Satz.
Williams (2011) beweist, dass ACC0 beinhaltet nicht Nexptime. Der Beweis verwendet viele Ergebnisse in der Komplexitätstheorie, einschließlich der Zeithierarchie Theorem, IP = PSPACE, Derandomisierungund die Darstellung von ACC0 über sym+ Schaltungen.[5] Murray & Williams (2018) verbessert diese Grenze und beweist das ACC0 Enthält kein NQP (nicht dunkleristische Quasipolynomzeit).
Es ist bekannt, dass Berechnung der Permanenten ist unmöglich für PROTOKOLLZEIT-uniform ACC0 Schaltungen, was impliziert, dass die Komplexitätsklasse Pp ist nicht in logime-uniformes ACC enthalten0.[6]
Anmerkungen
Verweise
- Allender, Eric (1996), "Komplexität der Schaltung vor dem Morgendämmerung des neuen Jahrtausends", 16. Konferenz über Grundlagen der Softwaretechnologie und theoretischer Informatik, Hyderabad, Indien, 18. bis 20. Dezember 1996 (PDF), Vorlesungsnotizen in Informatik, Vol. 1180, Springer, S. 1–18, doi:10.1007/3-540-62034-6_33
- Allender, Eric; Gore, Vivec (1994), "Ein gleichmäßiger Schaltkreis, der für die Permanent untergrenkt wird" (PDF), Siam Journal über Computing, 23 (5): 1026–1049, doi:10.1137/s0097539792233907
- Barrington, D.A. (1989), "Begrenzungsbreite Polynomgröße Verzweigungsprogramme erkennen genau diese Sprachen in NC an1" (PDF), Journal of Computer and System Sciences, 38 (1): 150–164, doi:10.1016/0022-0000 (89) 90037-8.
- Barrington, David A. Mix (1992), "Einige Probleme mit Razborov-Smolensky-Polynomen", in Paterson, M.S. (ed.), Boolesche Funktionskomplexität, Sel. Brei. Symp., Durham/UK 1990., London Mathematical Society Lecture Notes Series, Vol. 169, S. 109–128, ISBN 0-521-40826-1, Zbl 0769.68041.
- Barrington, D.A.; Thérien, D. (1988), "Finite Monoide und die Feinstruktur von NC1",", Journal of the ACM, 35 (4): 941–952, doi:10.1145/48014.63138
- Beigel, Richard; Tarui, Jun (1994), "auf ACC", Rechenkomplexität, 4 (4): 350–366, doi:10.1007/bf01263423.
- Clote, Peter; Kranakis, Evangelos (2002), Boolesche Funktionen und Berechnungsmodelle, Texte in theoretischer Informatik. Eine EATCS -Serie, Berlin: Springer-Verlag, ISBN 3-540-59436-1, Zbl 1016.94046
- Razborov, A. A. (1987), "Untergrenzen für die Größe der Schaltungen mit begrenzter Tiefe mit Basis {⊕, ∨}", Mathematik. Notizen der Akademie der Wissenschaft der UdSSR, 41 (4): 333–338.
- Smolensky, R. (1987), "Algebraische Methoden in der Theorie der unteren Grenzen für die boolesche Schaltungskomplexität", Proc. 19. ACM -Symposium über die Theorie des Computers, S. 77–82, doi:10.1145/28395.28404.
- Murray, Cody D.; Williams, Ryan (2018), "Circuit Lower Bounds für nichtdeterministische Quasi-Polytime: Ein leichtes Zeuge-Lemma für NP und NQP", Proc. 50. ACM -Symposium zur Theorie des Computers, S. 890–901, doi:10.1145/3188745.3188910, HDL:1721.1/130542
- Thérien, D. (1981), "Klassifizierung von endlichen Monoiden: Der Sprachansatz", Theoretische Informatik, 14 (2): 195–208, doi:10.1016/0304-3975 (81) 90057-8.
- Vollmer, Heribert (1999), Einführung in die Komplexität der Schaltung, Berlin: Springer, ISBN 3-540-64310-9.
- Williams, Ryan (2011), "Uneinheitliche ACC-Schaltkreis Untergrenzen" (PDF), IEEE -Konferenz zur Berechnung der Komplexität: 115–125, doi:10.1109/ccc.2011.36, ISBN 978-1-4577-0179-5.