NC (kompleksitet)

I kompleksitetsteori er et område med teoretisk datalogi , NC (for Nick's klasse ) en kompleksitetsklasse, der involverer parallelisme . Det er det sæt beslutningsproblemer, der besluttes i polylogaritmisk tid af et polynomisk antal maskiner parallelt. Det svarer til de problemer, der betragtes som lette at behandle ved hjælp af en parallel arkitektur. Klassen blev navngivet af Stephen Cook til ære for Nick Pippenger (in) , der arbejdede med emnet.

F.eks. Er (beslutningsproblemet forbundet med beregningen af) matrixproduktet i NC .

Definition

Et problem A er i NC, hvis der er to konstanter c og k, således at det er muligt at løse A på én gang ved hjælp af processorer parallelt. Vi kan give en mere præcis definition takket være boolske kredsløb . Ideen er, at to logiske porte kan beregne deres output parallelt. Så antallet af logiske porte er - groft sagt - antallet af processorer. Dybden af kredsløbet repræsenterer udførelsestiden. Mere præcist for alt definerer vi først klassen NC c som det sæt sprog, der er bestemt af en familie af kredsløb (hvor er størrelsen på input) kaldet ensartet (det vil sige, at vi faktisk kan beregne ud fra heltal ) af polynomstørrelse i og dybde . NC- klassen er så . $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 definitioner er ækvivalente.

Eksempler på problemer i NC

Beslutningsproblemerne i forbindelse med følgende beregningsproblemer er i NC:

tilføjelse af to heltal (mere præcist i AC 0 ), multiplikation af to heltal i NC 1, men ikke i AC 0 ;
tilføjelse af to matricer, multiplikation af to matricer;
beregne en maksimal kobling i en graf ;
N- bit paritetsfunktionen er i NC 1 : vi konstruerer, deler og erobrer et binært træ med en XOR-port, som kan omskrives med IKKE, OG og ELLER porte og derved opnår et kredsløb med højden O (log n ). Paritetsfunktionen er ikke i AC 0 .
I 1987 demonstrerede Buss, at evalueringen af en formel (dette er et specielt tilfælde af problemet med at evaluere et boolsk kredsløb , fordi en boolsk formel er et boolsk kredsløb, som er et træ) er komplet til ALOGTIME-klassen med reduktioner i logaritmisk tid (disse klasser i logaritmisk tid er defineret med Turing RAM-maskiner). ALOGTIME er lig med NC 1 med en vis ensartethed.

Forholdet til andre klasser

Følgende forhold er kendt, de bringer klasserne L , NL og P i spil :

{\ 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 klasserne AC jeg på en måde analog med NC og NC jeg bortset fra at arity af logiske gates er ubegrænset. 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øjagtigt den klasse af beslutningsproblemer, der er bestemt af en alternerende Turing-maskine i log n- rum med et antal alternationer (log n ) O (1) , det vil sige, at NC = STA (log n , *, ( log n ) O (1) ) hvor STA (s ( n ), t ( n ), a ( n )) er den klasse af beslutningsproblemer, der er bestemt af en alternerende Turing-maskine i rummet s ( n ), tid t ( n ) og veksler a ( n ).

Vi ved ikke, om NC er lig med P eller ikke. Som Arora og Barak angiver, ved vi ikke, hvordan NC 1 og polynomhierarkiet PH skal adskilles .

Åbent problem med sammenbruddet

Et vigtigt spørgsmål i kompleksitetsteori er, om indeslutningen af NC- hierarkiet er streng eller ej. Papadimitriou observerede, at hvis NC i = NC i +1 for nogle i , så NC i = NC j for alle j ≥ i , og dermed NC i = NC . Denne observation kaldes et sammenbrud af NC- hierarkiet, fordi kun en lighed i kæden af indeslutninger ${\ displaystyle {\ textbf {NC}} ^ {1} \ subseteq {\ textbf {NC}} ^ {2} \ subseteq \ cdots}$

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

indebærer, at hele NC- hierarkiet kollapser på niveau i . Så der er to muligheder:

${\ 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 inklusionerne i princippet er strenge (1) men der er ingen beviser.

Barringtons sætning

Barrington har vist, at den ikke-ensartede klasse NC svarer til de problemer, der er besluttet af tilsluttede programmer defineret som følger.

Eksternt link

(da) NC-klassen i Complexity Zoo

Noter og referencer

(in) " Mod en teori om kompleksitet synkron parallel beregning. » , Matematisk uddannelse , bind. 27,nitten og firs( læs online )
(i) Stephen A. Kog , " A taksonomi af problemer med hurtig parallelle algoritmer " , Information og Kontrol , Vol. 64, nr . 1,1 st januar 1985, s. 2–22 ( ISSN 0019-9958 , DOI 10.1016 / S0019-9958 (85) 80041-3 , læs online )
(i) Nicholas Pippenger , " er samtidige ressource grænser " , 20th Annual Symposium on Foundations of Computer Science (SFC'er 1979) ,1979, s. 307–311 ( ISSN 0272-5428 , DOI 10.1109 / SFCS.1979.29 , læs online )
(en) Sanjeev Arora og Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) 6.7.1.
(in) " Kursus - Læsning 2: Kompleksiteten af nogle problemer " [PDF] .
Samuel R. Buss , " Det boolske formelværdiproblem er i ALOGTIME " , på www.math.ucsd.edu ,Januar 1987(adgang til 5. maj 2017 )
(in) " Complexity Zoo: N - Complexity Zoo " , på complexityzoo.uwaterloo.ca (adgang til 29. oktober 2018 )
(in) " Boolske funktioner og beregningsmodeller - Springer " på link.springer.com (adgang til 9. juni 2016 ) .
(i) Walter L. Ruzzo , " One ensartet kompleksitet " , Journal of Computer og System Sciences , vol. 22, nr . 3,1 st juni 1981, s. 365–383 ( DOI 10.1016 / 0022-0000 (81) 90038-6 , læst online , adgang 30. oktober 2017 ).
(i) Dexter C. Közen , Theory of Computation , Springer Publishing Company, Incorporated,2010( ISBN 1849965714 og 9781849965712 , læs online ).