NC (kompleksitet)

I kompleksitetsteori er ett område med teoretisk informatikk , NC (for Nicks klasse ) en kompleksitetsklasse som involverer parallellisme . Det er settet med avgjørelsesproblemer som er bestemt i polylogaritmisk tid av et polynomisk antall maskiner parallelt. Det tilsvarer problemene som anses som lette å behandle av en parallell arkitektur. Klassen ble kåret av Stephen Cook til ære for Nick Pippenger (in) , som jobbet med emnet.

For eksempel er (beslutningsproblemet knyttet til beregningen av) matriksproduktet i NC .

Definisjon

Et problem A er i NC hvis det er to konstanter c og k slik at det er mulig å løse A på en gang ved hjelp av prosessorer parallelt. Vi kan gi en mer presis definisjon takket være boolske kretser . Tanken er at to logiske porter kan beregne produksjonen parallelt. Så antall logiske porter er - grovt sett - antall prosessorer. Dybden på kretsen representerer utførelsestiden. Mer presist, for alt , definerer vi først klassen NC c som settet med språk bestemt av en familie av kretser (hvor er størrelsen på inngangen) kalt uniform (det vil si at vi faktisk kan beregne ut fra heltall ) av polynomstørrelse i og dybde . NC- klassen er da . $O (\ log ^ {c} (n))$ $O (n ^ {k})$ $vs.$ ${\ displaystyle ({\ mathcal {C}} _ {n}) _ {n \ in \ mathbb {N}}}$ $ikke$ ${\ mathcal {C}} _ {n}$ $ikke$ $ikke$ $O (\ log ^ {c} (n))$ $\ cup _ {{c \ geq 1}} NC ^ {c}$

Disse to definisjonene er ekvivalente.

Eksempler på problemer i NC

Beslutningsproblemene knyttet til følgende beregningsproblemer er i NC:

tillegg av to heltall (mer presist i AC 0 ), multiplikasjon av to heltall i NC 1, men ikke i AC 0 ;
tillegg av to matriser, multiplikasjon av to matriser;
beregne en maksimal kobling i en graf ;
Paritetsfunksjonen til n biter er i NC 1 : vi konstruerer, deler og erobrer, et binært tre med en XOR-port, som kan skrives om med IKKE, OG og ELLER porter og dermed oppnå en krets med høyden O (log n ). Paritetsfunksjonen er ikke i AC 0 .
I 1987 demonstrerte Buss at evaluering av en formel (dette er et spesielt tilfelle av problemet med å evaluere en boolsk krets , fordi en boolsk formel er en boolsk krets som er et tre) er komplett for ALOGTIME-klassen med reduksjon i logaritmisk tid. (disse klassene i logaritmisk tid er definert med Turing RAM-maskiner). ALOGTIME er lik NC 1 med en viss ensartethet.

Forhold til andre klasser

Følgende forhold er kjent, de spiller inn klassene L , NL og 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}.}

Vi kan også definere klassen AC og klassene AC i på en måte som er analog med NC og NC i, bortsett fra at arten til de logiske portene er ubegrenset. Faktisk, som for alle i , har vi: AC = NC. ${\ displaystyle \ mathbf {NC} ^ {i} \ subseteq \ mathbf {AC} ^ {i} \ subseteq \ mathbf {NC} ^ {i + 1}}$

Ruzzo viste at NC er nøyaktig den klassen av beslutningsproblemer som er bestemt av en alternerende Turing-maskin i log n- rom med et antall alternasjoner (log n ) O (1) , det vil si at NC = STA (log n , *, ( log n ) O (1) ) der STA (s ( n ), t ( n ), a ( n )) er klassen av beslutningsproblemer bestemt av en alternerende Turing-maskin i rommet s ( n ), tid t ( n ) og vekslinger a ( n ).

Vi vet ikke om NC er lik P eller ikke. Som Arora og Barak spesifiserer, vet vi ikke hvordan vi skal skille NC 1 og polynomhierarkiet PH .

Åpent problem om sammenbruddet

Et viktig spørsmål i kompleksitetsteori er om inneslutningene i NC- hierarkiet er strenge eller ikke. Papadimitriou observerte at hvis NC i = NC i +1 for noen i , så NC i = NC j for alle j ≥ i , og dermed NC i = NC . Denne observasjonen kalles et kollaps av NC- hierarkiet fordi bare en likhet i kjeden av inneslutninger ${\ displaystyle {\ textbf {NC}} ^ {1} \ subseteq {\ textbf {NC}} ^ {2} \ subseteq \ cdots}$

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

innebærer at hele NC- hierarkiet kollapser på nivå i . Så det er to muligheter:

${\ 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}}}$

Forskerne tror at inneslutningene i prinsippet er strenge (1) men det er ingen bevis.

Barringtons teorem

Barrington har vist at den ikke-ensartede klasse NC tilsvarer problemene som er besluttet av tilkoblede programmer definert som følger.

Ekstern lenke

(en) NC-klassen i Complexity Zoo

Merknader og referanser

(in) " Mot en teori om kompleksitet synkron parallell beregning. » , Matematisk utdanning , vol. 27,nitten åtti en( les online )
(in) Stephen A. Cook , " A taxonomy of problems with fast parallel algorithms " , Information and Control , Vol. 64, n o 1,1 st januar 1985, s. 2–22 ( ISSN 0019-9958 , DOI 10.1016 / S0019-9958 (85) 80041-3 , les online )
(i) Nicholas Pippenger , " er samtidig ressurs grenser " , 20. Årlig Symposium on Foundations of Computer Science (SFCs 1979) ,1979, s. 307–311 ( ISSN 0272-5428 , DOI 10.1109 / SFCS.1979.29 , les online )
(en) Sanjeev Arora og Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) 6.7.1.
(i) " Course - Reading 2: kompleksiteten i noen problemer " [PDF] .
Samuel R. Buss , " Det boolske formelverdiproblemet er i ALOGTIME " , på www.math.ucsd.edu ,Januar 1987(åpnet 5. mai 2017 )
(in) " Complexity Zoo: N - Complexity Zoo " , på complexityzoo.uwaterloo.ca (åpnet 29. oktober 2018 )
(in) " Boolean Functions and Computation Models - Springer " på link.springer.com (åpnet 9. juni 2016 ) .
(in) Walter L. Ruzzo , " One uniform system complexity " , Journal of Computer and System Sciences , vol. 22, n o 3,1 st juni 1981, s. 365–383 ( DOI 10.1016 / 0022-0000 (81) 90038-6 , lest online , åpnet 30. oktober 2017 ).
(i) Dexter C. Közen , Theory of Computation , Springer Publishing Company, Incorporated,2010( ISBN 1849965714 og 9781849965712 , les online ).