AC0
AC 0 este o clasă de complexitate utilizată în complexitatea circuitului . Este cea mai mică clasă a ierarhiei AC și constă din toate familiile de circuite care au adâncimea O (1) și dimensiunea polinomială, cu porți ȘI și porți SAU cu un număr maxim nelimitat de linii de intrare ( fan-in ) (admitem uși NU numai la intrări). [1] Prin urmare, conține NC 0 , care are doar porți ȘI și SAU cu un număr maxim limitat de linii de intrare. [2]
Din punct de vedere al complexității descriptive, AC 0 uniform în DLOGTIME este egal cu clasa descriptivă FO + BIT a tuturor limbilor care pot fi descrise într-o logică de prim ordin cu adăugarea operatorului BIT , sau alternativ de FO ( +, ), sau de o mașină Turing în ierarhia logaritmică . [3]
În 1984 Furst, Saxe și Sipser au demonstrat că calcularea parității unei intrări nu poate fi decisă de niciun circuit AC 0 , chiar și cu neuniformitate. [4] [5] Rezultă că AC 0 nu este egal cu NC 1 , deoarece o familie de circuite din ultima clasă poate calcula paritatea. [1] Limitele mai precise decurg din lema comutației . Folosindu-le, s-a demonstrat că există o separare oracolă între PH și PSPACE .
Adunarea și scăderea numerelor întregi sunt calculabile în AC 0 , dar multiplicarea nu poate (cel puțin, nu conform reprezentărilor binare obișnuite sau ale bazei 10 ale numerelor întregi).
Notă
- ^ a b Arora & Barak (2009) p. 118
- ^ Arora și Barak (2009) p. 117
- ^ Neil Immerman, Complexitate descriptivă , New York, Springer-Verlag, 1999, p. 85, ISBN 9780387986005 .
- ^ Merrick Furst, James B. Saxe și Michael Sipser, Parity, circuits, and the polynomial-time hierarchy , in Math. Syst. Teorie , vol. 17, 1984, pp. 13-27, ISSN 0025-5661 , Zbl 0534.94008 .
- ^ Arora și Barak (2009) p. 287
linkuri externe
- Sanjeev Arora și Boaz Barak, Complexitatea calculațională. O abordare modernă , Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , Zbl 1193.68112 .
