AC (complexitate)

În complexitatea circuitelor , AC este o ierarhie a claselor de complexitate . Fiecare clasă, AC ⁱ , constă din limbaje recunoscute de circuitele booleene cu adâncime $O(\log ^{i}n)$ ${\ displaystyle O (\ log ^ {i} n)}$ ${\ displaystyle O (\ log ^ {i} n)}$ și un număr polinomial de porți AND și OR , cu un număr maxim nelimitat de linii de ventilare .

Numele „AC” a fost ales prin analogie cu NC , cu „A” în nume care înseamnă „alternativ” și se referă atât la alternanța dintre porțile ȘI ȘI SAU în circuite, cât și la mașinile Turing alternante . ^[1]

Clasa AC este AC ⁰ , care constă din circuite cu un număr maxim nelimitat de linii de intrare la adâncime constantă.

Ierarhia totală a claselor AC este definită ca

${\mbox{AC}}=\bigcup _{i\geq 0}{\mbox{AC}}^{i}$ ${\ displaystyle {\ mbox {AC}} = \ bigcup _ {i \ geq 0} {\ mbox {AC}} ^ {i}}$ ${\ displaystyle {\ mbox {AC}} = \ bigcup _ {i \ geq 0} {\ mbox {AC}} ^ {i}}$

Relația cu NC

Clasele AC sunt legate de clasele NC , care sunt definite în mod similar, dar cu porți care au doar un număr maxim constant de linii de intrare. Pentru fiecare i , avem ^[2] ^[3]

{\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{NC}}^{i+1}.

{\ displaystyle {\ mbox {NC}} ^ {i} \ subseteq {\ mbox {AC}} ^ {i} \ subseteq {\ mbox {NC}} ^ {i + 1}.}

{\ displaystyle {\ mbox {NC}} ^ {i} \ subseteq {\ mbox {AC}} ^ {i} \ subseteq {\ mbox {NC}} ^ {i + 1}.}

Ca o consecință imediată a acestui fapt, avem acel NC = AC. ^[4]

Se știe că incluziunea este rigidă pentru i = 0. ^[3]

Variații

Puterea claselor de curent alternativ poate fi influențată prin adăugarea de porturi suplimentare. Dacă adăugăm porți care calculează operația modulo pentru un modulo m , avem clasele ACC ⁱ [m] . ^[4]

Notă

^ Regan (1999) , pp. 27-18 .
^ Clote și Kranakis (2002) , p. 437 .
^ ^a ^b Arora și Barak (2009) , p. 118 .
^ ^a ^b Clote & Kranakis , p. 12 .

Bibliografie

Sanjeev Arora și Boaz Barak, Complexitatea calculațională. O abordare modernă , Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , Zbl 1193.68112 .
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 .
Kenneth W. Regan, Clase de complexitate , în Algoritmi și teoria teoriei calculului , CRC Press, 1999.
Heribert Vollmer, Introducere în complexitatea circuitelor. O abordare uniformă , Texte în informatică teoretică, Berlin, Springer-Verlag, 1998, ISBN 3-540-64310-9 , Zbl 0931.68055 .

Portal IT

Portalul de matematică

[1] Regan (1999) , pp. 27-18 .

[CK437-2] Clote și Kranakis (2002) , p. 437 .

[AB118-3] Arora și Barak (2009) , p. 118 .

[CK12-4] Clote & Kranakis , p. 12 .

[1]

[2]

[3]

[4]