ACC0
ACC 0 , uneori numit ACC , este o clasă de modele de calcul și probleme definite în complexitatea circuitelor , un domeniu de calcul teoretic. Clasa este definită prin creșterea clasei AC 0 de „circuite alternative” de adâncime constantă cu capacitatea de a număra; ACC înseamnă „AC cu contoare”. [1] În mod specific, o problemă aparține ACC 0 dacă poate fi rezolvată prin circuite de timp polinomial și adâncime constantă cu porți având un număr maxim limitat de linii de ventilare , inclusiv porți care numără modul un număr întreg fix. ACC 0 corespunde calculului în orice monoid rezolvabil. Clasa este foarte bine studiată în informatică teoretică datorită conexiunilor algebrice și deoarece este unul dintre cele mai mari modele de calcul concrete pentru care rezultă imposibilitatea de calcul, așa-numitele limite inferioare ale circuitelor.
Definiții
În mod informal, ACC 0 modelează clasa de calcule efectuate de circuite booleene cu adâncime constantă și dimensiune polinomială, unde porțile circuitelor includ „porți contoare modulare” care calculează numărul de intrări adevărate modulo unele constante fixe.
Mai formal, un limbaj aparține AC 0 [ m ] dacă poate fi calculat dintr-o familie de circuite C 1 , C 2 , ..., unde C n necesită n intrări, adâncimea fiecărui circuit este constantă, dimensiunea C n este o funcție polinomială a lui n , iar circuitul folosește următoarele porți: porți ȘI porți SAU cu număr maxim limitat de linii de intrare, care calculează conjuncția și disjuncția intrărilor; NU porți care calculează negarea singurei lor intrări; și porțile MOD- m cu număr maxim nelimitat de linii de intrare, care calculează 1 dacă numărul de intrare 1s este multiplu de m . O limbă aparține ACC 0 dacă aparține AC 0 [ m ] pentru unii m .
În unele texte, ACC i se referă la o ierarhie a claselor de circuite cu ACC 0 la nivelul său cel mai scăzut, unde circuitele din ACC i au adâncimea O (log i n ) și dimensiunea polinomială. [1]
Clasa ACC 0 poate fi definită și în termeni de calcule ale automatelor finite deterministe neuniforme (NUDFA) pe monoizi . În acest cadru, intrarea este interpretată ca elemente dintr-un monoid fix și intrarea este acceptată dacă produsul elementelor intrării aparține unei liste date de elemente ale monoidului. Clasa ACC 0 este familia de limbi acceptate de un NUDFA pe un anumit monoid care nu conține un grup de nerezolvat ca sub- grup . [2]
Puterea de calcul
Clasa ACC 0 include AC 0 . Această includere este strictă, deoarece o singură poartă MOD-2 calculează funcția de paritate, despre care se știe că este imposibil de calculat în AC 0 . Mai general, funcția MOD m nu poate fi calculată în AC 0 [ p ] pentru un număr prim p decât dacă m este o putere de p . [3]
Orice problemă din ACC 0 poate fi rezolvată prin circuite de adâncime 2, cu porți AND cu număr maxim de linii de intrare polilogaritmice la intrări, conectate la o singură poartă care calculează o funcție simetrică. [4] Aceste circuite se numesc circuite SYM + .
Clasa ACC 0 este inclusă în TC 0 .
Ryan Williams a anunțat în 2010 și a publicat în 2011 o demonstrație că ACC 0 nu conține NEXPTIME . [5] Dovada utilizează numeroase rezultate în teoria complexității, inclusiv teoria ierarhiei timpului , IP = PSPACE , derandomizare și idei în dovada teoremei lui Toda . [6]
Se știe că calculul permanentului este imposibil pentru circuite ACC 0 uniforme în timp logaritmic, ceea ce implică faptul că clasa de complexitate PP nu este conținută în ACC 0 uniformă în timp logaritmic. [7]
Se presupune că ACC 0 nu poate calcula funcția majoritară a veniturilor sale, dar această întrebare nu a fost rezolvată din iulie 2012.
Notă
Bibliografie
- Eric Allender , Complexitatea circuitului înainte de apariția noului mileniu ( PDF ), în a 16-a Conferință despre fundamentele tehnologiei software și informaticii teoretice, Hyderabad, India, 18-20 decembrie 1996 , Lecture Notes in Computer Science, vol. 1180, Springer, 1996, 1-18, DOI : 10.1007 / 3-540-62034-6_33 .
- Eric Allender și Vivec Gore, Un circuit uniform de limită inferioară pentru permanent ( PDF ), în SIAM Journal on Computing , vol. 23, n. 5, 1994, 1026-1049, DOI : 10.1137 / S0097539792233907 .
- DA Barrington, Programele de ramificare de dimensiuni polinomiale cu lățime limitată recunosc exact acele limbi în NC 1 ( PDF ), în Journal of Computer and System Sciences , vol. 38, nr. 1, 1989, 150-164, DOI : 10.1016 / 0022-0000 (89) 90037-8 .
- David A. Mix Barrington, Unele probleme care implică polinoame Razborov-Smolensky , în MS Paterson (ed.), Complexitatea funcției booleene, Sel. Pap. Symp., Durham / UK 1990 , London Mathematical Society Lecture Notes Series, vol. 169, 1992, 109-128, ISBN 0-521-40826-1 , Zbl 0769.68041 .
- DA Barrington și D. Thérien, monoizi finiti și structura fină a NC 1 , în Jurnalul ACM , vol. 35, nr. 4, 1988, 941-952, DOI : 10.1145 / 48014.63138 .
- Richard Beigel și Jun Tarui, Despre ACC , în Computational Complexity , vol. 4, 1994, 350–366, DOI : 10.1007 / BF01263423 .
- Peter Clote și Evangelos Kranakis, funcții booleene și modele de calcul , Texte în informatică teoretică. O serie EATCS, Berlin, Springer-Verlag, 2002, ISBN 3-540-59436-1 , Zbl 1016.94046 .
- AA Razborov , limite inferioare pentru mărimea circuitelor de adâncime mărginită cu baza {⊕, ∨} , în matematică. note ale Academiei de Științe a URSS , vol. 41, nr. 4, 1987, 333–338.
- R. Smolensky, Metode algebrice în teoria limitelor inferioare pentru complexitatea circuitului boolean , în Proc. 19th ACM Symposium on Theory of Computing , 1987, 77-82, DOI : 10.1145 / 28395.28404 .
- D. Thérien, Clasificarea monoizilor finiti: abordarea limbajului , în Teoria Informaticii , vol. 14, n. 2, 1981, 195–208, DOI : 10.1016 / 0304-3975 (81) 90057-8 .
- Heribert Vollmer, Introducere în complexitatea circuitului , Berlin, Springer, 1999, ISBN 3-540-64310-9 .
- Ryan Williams , Circuite ACC neuniforme Limite inferioare ( PDF ), în IEEE Conf. On Computational Complexity , 2011, 115-125, DOI : 10.1109 / CCC.2011.36 .
