NC (összetettség)

A komplexitáselméletben az elméleti számítástechnika egyik területe , az NC ( Nick osztálya szempontjából ) a párhuzamosságot magában foglaló komplexitási osztály . Ez a döntési problémák összessége , amelyet polilogaritmikus időben egy polinomszámú gép párhuzamosan dönt . Megfelel a párhuzamos architektúra által könnyen kezelhetőnek tartott problémáknak. Az osztályt Stephen Cook nevezte el Nick Pippenger (in) tiszteletére , aki a témával foglalkozott.

Például, a (döntési probléma társított számítás a) mátrix termék van NC .

Meghatározás

Az A probléma az NC-ben van, ha két c és k konstans van , így A processzorok párhuzamos használatával egyszerre megoldható az A. A logikai áramköröknek köszönhetően pontosabb meghatározást adhatunk . Az ötlet az, hogy két logikai kapu párhuzamosan kiszámíthatja a kimenetét. Tehát a logikai kapuk száma - durván szólva - a processzorok száma. Az áramkör mélysége a végrehajtási időt jelenti. Pontosabban, mindenre előbb meghatározzuk az NC c osztályt, mint a nyelvek halmazát, amelyet egy áramkörcsalád határoz meg (hol van a bemenet mérete), amelyet egységesnek nevezünk (vagyis azt, hogy a egész szám ) polinomi méretű és mélységű . Az NC osztály akkor . $O (\ log ^ {c} (n))$ $O (n ^ {k})$ $vs.$ ${\ displaystyle ({\ mathcal {C}} _ {n}) _ {n \ in \ mathbb {N}}}$ $nem$ ${\ mathcal {C}} _ {n}$ $nem$ $nem$ $O (\ log ^ {c} (n))$ $\ cup _ {{c \ geq 1}} NC ^ {c}$

Ez a két meghatározás egyenértékű.

Példák az NC problémáira

A következő számítási problémákkal kapcsolatos döntési problémák az NC-ben vannak:

két egész összeadása (pontosabban az AC 0-ban ), két egész szám szorzata az NC 1-ben, de az AC 0-ban nem ;
két mátrix összeadása, két mátrix szorzása;
számítsa ki a maximális kapcsolást egy grafikonon ;
Az n bit paritásfüggvénye az NC 1-ben van : megépítünk, felosztunk és meghódítunk egy bináris fát egy XOR kapuval, amelyet a NOT, AND és OR kapukkal átírhatunk, és így O (log n ) magasságú áramkört kapunk . A paritásfüggvény nincs AC 0-ban .
1987-ben Buss bebizonyította, hogy egy képlet kiértékelése (ez egy speciális esete a logikai áramkör kiértékelésének problémájának , mert a logikai képlet egy logikai áramkör, amely egy fa) teljes az ALOGTIME osztály számára, logaritmikus idő csökkenéssel (ezeket az osztályokat a logaritmikus időben a Turing RAM gépek határozzák meg). Az ALOGTIME egyenlő az NC 1- vel, az egyenletesség bizonyos feltételeivel.

Kapcsolatok más osztályokkal

A következő összefüggések ismertek, ezek az L , NL és P osztályokat hozzák játékba :

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

Az AC és az AC i osztályokat az NC és az NC i analóg módon is meghatározhatjuk, azzal a különbséggel, hogy a logikai kapuk aritása nincs korlátozva. Valójában, mint minden i esetében: AC = NC. ${\ displaystyle \ mathbf {NC} ^ {i} \ subseteq \ mathbf {AC} ^ {i} \ subseteq \ mathbf {NC} ^ {i + 1}}$

Ruzzo megmutatta, hogy az NC pontosan az a döntési probléma osztálya, amelyet egy váltakozó Turing-gép log n térben , számos váltakozással (log n ) O (1) határoz meg , vagyis NC = STA (log n , *, ( log n ) O (1) ) ahol az STA (s ( n ), t ( n ), a ( n )) az a döntési probléma osztály, amelyet egy váltakozó Turing-gép döntött az s ( n ), t ( n ) időben és a ( n ) váltakozások .

Nem tudjuk, hogy NC egyenlő-e P-vel vagy sem. Ahogy Arora és Barak meghatározza, nem tudjuk, hogyan kell elválasztani az NC 1-t és a PH polinomiális hierarchiát .

Nyitott probléma az összeomlással kapcsolatban

A komplexitáselmélet egyik fontos kérdése, hogy az NC hierarchia zárványai szigorúak-e vagy sem. Papadimitriou megfigyelte, hogy ha NC i = NC i +1 néhány i-re , akkor NC i = NC j minden j ≥ i-re , és így NC i = NC . Ezt a megfigyelést az NC hierarchia összeomlásának nevezik, mert a zárványok láncolatában csak egy egyenlőség van ${\ displaystyle {\ textbf {NC}} ^ {1} \ subseteq {\ textbf {NC}} ^ {2} \ subseteq \ cdots}$

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

azt jelenti, hogy a teljes NC hierarchia összeomlik az i szinten . Tehát két lehetőség van:

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

A kutatók szerint hogy elvileg a zárványok szigorúak (1), de nincsenek bizonyítékok.

Barrington tétele

Barrington bebizonyította, hogy az egyenetlen NC osztály megfelel az összekapcsolt programok által az alábbiakban meghatározott problémáknak.

Külső hivatkozás

(en) Az NC osztály a Komplexitás Állatkertben

Megjegyzések és hivatkozások

(in) " A komplexitás elmélete felé szinkron párhuzamos számítás. » , Matematikai oktatás , vol. 27,tizenkilenc nyolcvan egy( online olvasás )
(in) Stephen A. Cook , " A taxonómia problémák gyors párhuzamos algoritmusok " , tájékoztató és ellenőrző , Vol. 64, n o 1,1 st január 1985, P. 2–22 ( ISSN 0019-9958 , DOI 10.1016 / S0019-9958 (85) 80041-3 , online olvasás )
(in) Nicholas Pippenger , " az erőforrások egyidejű korlátjai " , 20. éves szimpózium a számítástechnika alapjairól (SFCs 1979) ,1979, P. 307–311 ( ISSN 0272-5428 , DOI 10.1109 / SFCS.1979.29 , online olvasás )
(en) Sanjeev Arora és Boaz Barak , Számítási komplexitás: modern megközelítés , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) 6.7.1.
(in) " Tanfolyam - 2. olvasás: Néhány probléma összetettsége " [PDF] .
Samuel R. Buss , „ A Boole-formulával érték probléma van ALOGTIME ” , a www.math.ucsd.edu ,1987. január(megtekintve 2017. május 5-én )
(in) " Complexity Zoo: N - Complexity Zoo " , a complexityzoo.uwaterloo.ca webhelyen (hozzáférés: 2018. október 29. )
(in) " Boolean Functions and Computation Models - Springer " a link.springer.com webhelyen (hozzáférés: 2016. június 9. ) .
(in) Walter L. Ruzzo , " Egy egységes rendszer komplexitás " , Journal of Computer and System Sciences , vol. 22, n o 3,1 st június 1981, P. 365–383 ( DOI 10.1016 / 0022-0000 (81) 90038-6 , online olvasás , hozzáférés : 2017. október 30 ).
(in) Dexter C. Kozen , digitális számítás elmélete , Springer Publishing Company, Incorporated,2010( ISBN 1849965714 és 9781849965712 , online olvasás ).