NC (complexitate)

În teoria complexității , un domeniu al informaticii teoretice , NC (pentru clasa lui Nick ) este o clasă de complexitate care implică paralelism . Este ansamblul problemelor decizionale decise în timp polilogaritmic de un număr polinomial de mașini în paralel. Corespunde problemelor considerate ușor de tratat de o arhitectură paralelă. Clasa a fost numită de Stephen Cook în onoarea lui Nick Pippenger (în) , care a lucrat la acest subiect.

De exemplu, (problema de decizie asociată cu calculul) produsului matricial este în NC .

Definiție

O problemă A este în NC dacă există două constante c și k astfel încât este posibil să se rezolve A într-o singură dată folosind procesoare în paralel. Putem da o definiție mai precisă grație circuitelor booleene . Ideea este că două porți logice își pot calcula ieșirea în paralel. Deci, numărul de porți logice este - aproximativ vorbind - numărul de procesoare. Adâncimea circuitului reprezintă timpul de execuție. Mai exact, pentru orice , mai întâi definim clasa NC c ca setul de limbaje decis de o familie de circuite (unde este dimensiunea intrării) numită uniformă (adică că putem calcula efectiv din întreg ) de dimensiunea și adâncimea polinomului . Clasa NC este atunci . $O (\ log ^ {c} (n))$ $O (n ^ {k})$ $vs.$ ${\ displaystyle ({\ mathcal {C}} _ {n}) _ {n \ in \ mathbb {N}}}$ $nu$ ${\ mathcal {C}} _ {n}$ $nu$ $nu$ $O (\ log ^ {c} (n))$ $\ cup _ {{c \ geq 1}} NC ^ {c}$

Aceste două definiții sunt echivalente.

Exemple de probleme în NC

Problemele de decizie asociate cu următoarele probleme de calcul sunt în NC:

adunarea a două numere întregi (mai precis în AC 0 ), înmulțirea a două numere întregi în NC 1 dar nu în AC 0 ;
adunarea a două matrice, multiplicarea a două matrice;
calculați o cuplare maximă într-un grafic ;
Funcția de paritate n- bit este în NC 1 : construim, împărțim și cucerim, un arbore binar cu o poartă XOR, care poate fi rescris cu porțile NOT, AND și OR și astfel obținem un circuit de înălțime O (log n ). Funcția de paritate nu este în AC 0 .
În 1987, Buss a demonstrat că evaluarea unei formule (acesta este un caz special al problemei evaluării unui circuit boolean , deoarece o formulă booleană este un circuit boolean care este un arbore) este completă pentru clasa ALOGTIME cu reduceri ale timpului logaritmic (aceste clase în timp logaritmic sunt definite cu mașinile Turing RAM). ALOGTIME este egal cu NC 1 cu o anumită condiție de uniformitate.

Relațiile cu alte clase

Sunt cunoscute următoarele relații, acestea pun în joc clasele L , NL și P :

{\ displaystyle \ mathbf {NC} ^ {1} \ subseteq \ mathbf {L} \ subseteq \ mathbf {NL} \ subseteq \ mathbf {AC} ^ {1} \ subseteq \ mathbf {NC} ^ {2} \ subseteq \ mathbf {NC} \ subseteq \ mathbf {P}.}

Clasa AC și clasele AC i pot fi, de asemenea, definite într-un mod analog NC și NC i, cu excepția faptului că aritatea porților logice este nelimitată. De fapt, așa cum , pentru tot i , avem: AC = NC. ${\ displaystyle \ mathbf {NC} ^ {i} \ subseteq \ mathbf {AC} ^ {i} \ subseteq \ mathbf {NC} ^ {i + 1}}$

Ruzzo a arătat că NC este exact clasa problemelor de decizie decise de o mașină alternativă Turing în spațiul log n cu un număr de alternanțe (log n ) O (1) , adică NC = STA (log n , *, ( log n ) O (1) ) unde STA (s ( n ), t ( n ), a ( n )) este clasa problemelor de decizie decise de o mașină alternativă de Turing în spațiul s ( n ), timpul t ( n ) și alternanțele a ( n ).

Nu știm dacă NC este egal cu P sau nu. După cum specifică Arora și Barak, nu știm cum să separăm NC 1 și ierarhia polinomială PH .

Problemă deschisă despre prăbușire

O întrebare importantă în teoria complexității este dacă incluziunile ierarhiei NC sunt stricte sau nu. Papadimitriou a observat că, dacă NC i = NC i +1 pentru unele i , atunci NC i = NC j pentru toate j ≥ i , și astfel, NC i = NC . Această observație se numește colaps al ierarhiei NC , deoarece o singură egalitate în lanțul incluziunilor ${\ displaystyle {\ textbf {NC}} ^ {1} \ subseteq {\ textbf {NC}} ^ {2} \ subseteq \ cdots}$

{\ displaystyle {\ textbf {NC}} ^ {1} \ subseteq {\ textbf {NC}} ^ {2} \ subseteq \ cdots}

implică faptul că întreaga ierarhie NC se prăbușește la nivelul i . Astfel, există două posibilități:

${\ displaystyle {\ textbf {NC}} ^ {1} \ subset \ cdots \ subset {\ textbf {NC}} ^ {i} \ subset ... \ subset {\ textbf {NC}} ^ {i + j } \ subset \ cdots {\ textbf {NC}}}$
${\ displaystyle {\ textbf {NC}} ^ {1} \ subset \ cdots \ subset {\ textbf {NC}} ^ {i} = ... = {\ textbf {NC}} ^ {i + j} = \ cdots {\ textbf {NC}}}$

Cercetătorii cred că a priori incluziunile sunt stricte (1) dar nu există dovezi.

Teorema lui Barrington

Barrington a arătat că clasa NC neuniformă corespunde problemelor decise de programele conectate definite după cum urmează.

Link extern

(ro) Clasa NC de la complexitatea zoologică

Note și referințe

(în) „ Către o teorie a calculului paralel sincron al complexității. » , Educație matematică , vol. 27,nouăsprezece optzeci și unu( citește online )
(în) Stephen A. Cook , " O taxonomie a problemelor cu algoritmi rapidi paraleli " , Information and Control , Vol. 64, n o 1,1 st ianuarie 1985, p. 2–22 ( ISSN 0019-9958 , DOI 10.1016 / S0019-9958 (85) 80041-3 , citiți online )
(în) Nicholas Pippenger , „ este o limită simultană a resurselor ” , al 20-lea Simpozion anual privind fundamentele științei computerelor (SFCs 1979) ,1979, p. 307–311 ( ISSN 0272-5428 , DOI 10.1109 / SFCS.1979.29 , citiți online )
(en) Sanjeev Arora și Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) 6.7.1.
(în) „ Curs - Lectura 2: Complexitatea unor probleme ” [PDF] .
Samuel R. Buss , „ Problema valorii formulei booleene este în ALOGTIME ” , la www.math.ucsd.edu ,Ianuarie 1987(accesat la 5 mai 2017 )
(în) „ Complexity Zoo: N - Complexity Zoo ” , pe complexzozoo.uwaterloo.ca (accesat la 29 octombrie 2018 )
(în) „ Funcții booleene și modele de calcul - Springer ” pe link.springer.com (accesat la 9 iunie 2016 ) .
(în) Walter L. Ruzzo , „ One uniform system complex ” , Journal of Computer and System Sciences , vol. 22, n o 3,1 st iunie 1981, p. 365–383 ( DOI 10.1016 / 0022-0000 (81) 90038-6 , citit online , accesat la 30 octombrie 2017 ).
(în) Dexter C. Kozen , Theory of Computation , Springer Publishing Company, Incorporated,2010( ISBN 1849965714 și 9781849965712 , citiți online ).