AC 0


În teoria complexității , AC 0 este o clasă de complexitate definită de circuite booleene de adâncime constantă. Face parte din ierarhia AC . Clasa AC 0 conține adunarea, dar nu funcția de paritate, multiplicarea sau predicatul de primalitate (vezi mai jos).

Definiție

Clasa AC 0 este clasa de complexitate a problemelor determinate de circuite boolean de adâncime constantă, dimensiunea polinomială, porțile sunt AND și OR , grade sosesc nemărginit (de fapt , alte uși pot fi permise ca „ SAU exclusiv “ sau NU porti , deoarece acestea sunt expresibil, fără a schimba complexitatea, prin ȘI și SAU ). Acronimul AC provine din circuitul de alternanță . Face parte din ierarhia AC .

Exemple

Adăugarea este în AC 0 . Mai precis, pentru orice i, problema de decizie care ia ca biți de intrare 2n care reprezintă două numere a și b de n biți și care calculează i - lea bit de suma a și b este în curent alternativ 0 .

Detalii despre un circuit de dimensiune polinomială și adâncime constantă pentru adăugare

Aici este o modalitate de a construi un circuit pentru a calcula i - lea bit al sumei unui n-1 ... un 0 și b n-1 ... b 0 . Rețineți ∧ "și" logica, ∨ logica "sau" și ⊕ exclusiv sau. Considerăm un j ca o propunere, adevărat dacă j - lea bit de un este egal cu 1, și false în caz contrar. De asemenea, b j ca o propunere, adevărat dacă j - lea bit de b este egal cu 1, și false în caz contrar. De asemenea, vom nota prin e j ca o propunere, adevărat dacă j - lea bit de s este 1, și false în caz contrar. Introducem și alte propuneri:

Avem :

Numărul de porți din circuit corespunzător formulelor de mai sus este polinomial în n. De asemenea, adâncimea circuitului este constantă așa cum se arată în circuitul prezentat în ilustrația de mai sus.

 

De asemenea, scăderea este în AC 0 .

Exemple de probleme non-AC 0

Paritate

Funcția de paritate este un predicat care returnează 1 dacă în intrare numărul de biți 1 este par și care returnează 0 altfel. În anii 1970 , nu se știa dacă există circuite AC 0 pentru problema clicii sau problema vânzătorului călător . De fapt, Furst, Saxe și Sipser și independent Miklós Ajtai au arătat că nu este cazul. Au demonstrat chiar că un predicat mult mai simplu, și anume funcția de paritate , nu aparține AC 0 . Johan Håstad a arătat apoi un rezultat mai puternic, lema de schimbare  (în) . Deoarece funcția de paritate este în NC 1 , deducem că includerea AC 0 în NC 1 este strictă.

Majoritate

Funcția majoritară ia n biți ca intrare și returnează 1 dacă strict mai mult de jumătate din biți sunt egali cu 1. Această funcție nu este în AC 0 . Putem demonstra acest lucru în mod absurd, dacă majoritatea este în AC 0 , adăugând biți suplimentari, putem testa dacă x ≥ k , unde x este numărul întreg reprezentat de biții în cauză și k este o constantă; de acolo putem testa dacă x = k  ; și, prin urmare, testați paritatea , în timp ce vă aflați în AC 0 , ceea ce este o contradicție.

Multiplicare

Înmulțirea nu este în AC 0 și se arată prin reducerea din funcția de paritate. Pe de altă parte, este în NC 1 .

Primalitate

Predicatul de primalitate care testează dacă un număr întreg este prim nu se află în AC 0 .

Complexitate descriptivă

Clasa AC 0 este legată de logica primului ordin în complexitate descriptivă .

Note și referințe

  1. (en) Sanjeev Arora și Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , cap.  14 („Limitele inferioare ale circuitului”) , p.  248
  2. Sylvain Perifel , algoritmice complexitate , elipse ,2014, 432  p. ( ISBN  9782729886929 , citit online ) , cap.  5 („Uniformitate și neuniformitate”)
  3. (în) „  Curs Arnsfelt Kristoffer Hansen AC  ” pe site-ul Arnsfelt Kristoffer Hansen la Universitatea Aarhus (Dannemark) , p.  2
  4. Merrick Furst , James B. Saxe și Michael Sipser , „  Parity, circuits, and the polynomial-time hierarchy  ”, Math. Syst. Teorie , vol.  17,1984, p.  13-27 ( ISSN  0025-5661 , DOI  10.1007 / bf01744431 , zbMATH  0534.94008 )
  5. Miklós Ajtai , „  ∑ 1 1-formule pe structuri finite  ”, Analele logicii pure și aplicate , vol.  24, n o  1,1983, p.  1-48
  6. Johan Håstad , „ Limite inferioare aproape optime pentru circuite cu adâncime mică” , în Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing, 28-30 mai 1986, Berkeley, California, {SUA} ,1986( DOI  10.1145 / 12130.12132 ) , p.  6-20
  7. (în) „  Lectura 3: AC0, lema de schimbare  ”
  8. (în) „  Citirea este 5 AC0 și TC0  ”
  9. Eric Allender , Michael Saks și Igor Shparlinski , „  A Lower Bound for Primality  ”, Journal of Computer and System Sciences , vol.  62,1 st martie 2001, p.  356-366 ( DOI  10.1006 / jcss.2000.1725 , citit online , accesat la 28 iunie 2016 )
  10. (în) Neil Immerman , Complexitate descriptivă , New York, Springer-Verlag ,1999, 268  p. ( ISBN  0-387-98600-6 , prezentare online ).

Link extern