Î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).
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 .
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ăugareAici 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 .
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ă.
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.
Î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 .
Predicatul de primalitate care testează dacă un număr întreg este prim nu se află în AC 0 .
Clasa AC 0 este legată de logica primului ordin în complexitate descriptivă .