NC osztály

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. május 31-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A számítási bonyolultság elméletében az NC osztály (az angol Nick's Class szóból ) azon megoldhatósági problémák összessége , amelyek polilogaritmikus időben megoldhatók egy párhuzamos számítógépen , polinomiális számú processzorral. Más szóval, egy probléma akkor tartozik az NC osztályba, ha vannak olyan állandók , amelyek párhuzamos processzorokkal időben megoldhatók . Stephen Cook [1] [2] Nick Pippenger után nevezte el "Nick osztályának" , aki kiterjedt kutatásokat végzett [3] a polilogmélységű és polinomméretű áramkörökről. [négy] $k$ $c$ $O(\log ^{c}n)$ $O(n^{k})$

Ahogyan a P osztályt képlékeny problémák osztályának tekinthetjük ( Cobham tézise ), úgy az NC-t is úgy lehet felfogni, mint egy párhuzamos számítógépen hatékonyan megoldható problémák osztályát. [5] Az NC a P részhalmaza, mivel párhuzamos polilog számítások szimulálhatók szekvenciális polinomszámításokkal. Nem ismert, hogy NP = P igaz-e, de a legtöbb tudós úgy véli, hogy nem, ami azt jelenti, hogy valószínűleg vannak olyan alakítható feladatok, amelyek „természetüknél fogva” egymás után következnek, és nem gyorsíthatók fel a párhuzamosság segítségével. Ahogyan az NP-teljes problémák osztályát a "legvalószínűbben megoldhatatlan" problémák osztályának tekinthetjük, úgy a P-teljes problémák osztályát NC-re redukálva úgy tekinthetjük, mint "nagy valószínűséggel nem párhuzamosítható" vagy "valószínűleg szekvenciális természetű".

A definícióban szereplő párhuzamos számítógép párhuzamos véletlen hozzáférésű gépnek tekinthető ( PRAM - az angol parallel, random-access gépből). Ez egy párhuzamos számítógép központi memóriatárral, amelynek bármely processzora állandó időben bármely bithez hozzáfér. Az NC definícióját nem befolyásolja az, hogy a PRAM hogyan éri el ugyanazt a bitet több processzorról egyszerre.

Az NC úgy definiálható , mint a polilogaritmikus mélységű és polinomiális számú kapuval rendelkező elosztott Boole - áramkör által megoldható megoldhatósági problémák halmaza .

Feladatok az NC-ben

Az NC számos feladatot tartalmaz, többek között:

Egész számok összeadása, szorzása és osztása;
Mátrixszorzás , rangjuk megszámlálása, determináns, inverz mátrix ;
polinom gcd ;
A maximális egyezés megtalálása.

Gyakran ezekre a problémákra az algoritmusokat külön-külön gondolták ki, és nem lehet az ismert algoritmusok naiv adaptációja - a Gauss-módszer és az Euklidész-algoritmus arra a tényre támaszkodik, hogy a műveleteket szekvenciálisan hajtják végre.

Hierarchia NC

Az NC i olyan megoldhatósági problémák halmaza, amelyek polinomiális számú kapuval (legfeljebb két bemenettel) és mélységgel , vagy egy párhuzamos számítógéppel, polinomszámú processzorral időben megoldhatók . Nyilvánvalóan, $O(\log ^{i}n)$ $O(\log ^{i}n)$

{\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\ mathsf {NC}},

mi az NC hierarchia.

Az NC osztályokat az L , NL [6] és AC [7] tárolási osztályokhoz rendelhetjük :

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

Az NC és AC osztályok azonosak, kivéve az AC osztályhoz tartozó szelepbemenetek korlátlan számát. Mindegyikre az [5] [7] igaz : $én$

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

Ennek következménye az NC = AC . [8] Ismeretes, hogy mindkét zárvány szigorú a -ra . [5] Hasonlóképpen megkaphatjuk, hogy az NC ekvivalens a változó Turing-gépen megoldott feladatsorral , lépésenként legfeljebb két választási lehetőséggel, O (log n ) memóriával és változtatásokkal. [9] $i=0$ ${\displaystyle (\log n)^{O(1)))$

Megoldatlan probléma: natív az NC?

A számítási komplexitáselmélet egyik nagy nyitott kérdése az , hogy az NC-hierarchia minden beágyazása megfelelő-e. Amint Papadimitriou megjegyezte, ha NC i = NC i +1 igaz néhányra , akkor NC i = NC j mindegyikre , és ennek következtében NC i = NC . Ezt a megfigyelést NC-hierarchia hajtogatásának nevezik, mert még az egymásba ágyazó lánc egyetlen egyenlőségéből is: $én$ $j\geqslant i$

{\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots

ebből következik, hogy a teljes NC -hierarchia valamilyen szintre "összeomlik" . Így két lehetőség lehetséges: $én$

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

Széles körben elterjedt az a vélemény, hogy az (1) igaz, bár még nem találtak bizonyítékot egyik állítás igazságosságára sem.

Barrington tétele

A változó, szélesség és hosszúságú elágazó program hosszúságú utasítások sorozatából áll . Minden utasítás egy hármas , ahol az ellenőrizni kívánt változó indexe , és a és a permutációs függvények -tól -ig . A számokat az elágazó program állapotainak nevezzük. A program az 1-es állapotban indul, és minden utasítás állapotát vagy -ra változtatja , attól függően, hogy a -edik változó 0-val vagy 1-gyel egyenlő-e. $n$ $k$ $m$ $m$ ${\megjelenítési stílus (i,p,q)}$ $én$ $(1\leq i\leq n)$ $p$ $q$ $\{1,2,...,k\}$ $\{1,2,...,k\}$ $1,2,...,k$ ${\megjelenítési stílus (i,p,q)}$ $x$ $p(x)$ $q(x)$ $én$

Az elágazó programok családja elágazó programokból áll, mindegyikhez változókkal . $n$ $n$

Könnyen kimutatható, hogy bármely nyelv felismerhető egy 5-ös szélességű és exponenciális hosszúságú elágazó programcsaládról, vagy egy exponenciális szélességű és lineáris hosszúságú elágazó programcsaládról. $L$ $\{0,1\}$

Minden reguláris nyelv nem ismerhető fel állandó szélességű, lineáris utasításokat elágazó programok családjaként (mivel a DFA átalakítható elágazó programmá). A BWBP olyan nyelvosztályt jelöl, amelyet a BWBP (korlátozott szélesség és polinomiális hossz) elágazó programok családja ismer fel. [10] . $\{0,1\}$

Barrington tétele [11] kimondja, hogy a BWBP pontosan allokálatlan NC 1 . A tétel bizonyítása a szimmetriacsoport eldönthetetlenségét használja fel . [tíz] $S_{5}$

A Barrington-tétel bizonyítása

Bizonyítsuk be, hogy egy állandó szélességű és polinomméretű elágazó program ( VP ) NC 1 -ből áramkörré alakítható .

Ellenkezőleg: legyen egy C áramkör az NC 1 -ből . Az általánosság elvesztése nélkül feltételezzük, hogy csak ÉS és NEM kapukat használunk benne.

Definíció: A VI-t Boole-függvény kiszámításának nevezzük, vagy ha az eredményt adja , akkor az azonos permutációt , az eredményéhez pedig a -permutációt . Mivel a C sémánk néhány logikai függvényt ír le , és csak azt, ezeket a kifejezéseket felcserélhetjük. $\sigma$ $f$ $(\sigma -f)$ $f=0$ $f=1$ $\sigma$ $f$

A bizonyításhoz két lemmát fogunk használni:

1. lemma : Ha van olyan VP, amely -számítja , akkor létezik olyan VP is, amely -kalkulál (vagyis egyenlő at , és egyenlő . $\sigma$ $f$ $\sigma ^{-1}$ $f$ $id$ $f=0$ $\sigma ^{-1}$ $f=1$

Bizonyítás : mivel a és a ciklusok, és bármely két ciklus konjugált , akkor van olyan permutáció , hogy = . Ezután megszorozzuk a permutációkkal és a bal oldali első VP utasítással (hogy megkapjuk a permutációkat és ), majd az utolsó utasításból származó permutációkat megszorozzuk a jobb oldalival ( és kapjuk ). Ha korábban cselekedeteink (az általánosság elvesztése nélkül) egyenlő volt -vel, akkor most az eredmény , ha pedig egyenlő volt -vel, akkor az eredmény egyenlő -vel . Így kaptunk egy VI-t, amely -calculates , ugyanolyan hosszúsággal (az utasítások száma nem változott). $\sigma$ $\sigma ^{-1}$ $\pi$ $\sigma ^{-1}$ $\pi \sigma \pi ^{-1}$ $\pi$ $p_{1}$ $q_{1}$ ${\pi }p_{1}$ ${\pi }q_{1}$ $\pi ^{-1}$ ${\displaystyle p_{n}\pi ^{-1))$ ${\displaystyle q_{n}\pi ^{-1))$ ${p_{1}}{p_{2}}...{p_{n}}$ $id$ ${\pi }id{\pi }^{-1}=id$ $\sigma$ ${\displaystyle \pi \sigma \pi ^{-1}=\sigma ^{-1))$ $\sigma ^{-1}$ $f$

Megjegyzés : ha a VP kimenetét megszorozzuk a jobbal , akkor nyilvánvaló módon megkapjuk a VP, -calculating függvényt . $(\sigma ^{-1}-f)$ $\sigma$ $\sigma$ ${\neg }f$

2. lemma : Ha két VI van: -számítás és -számítás hosszúságokkal és , ahol és 5-ciklusos permutáció, akkor létezik olyan VI 5-ciklusos permutációval , hogy a VI -számítja , és mérete nem haladja meg + . $\sigma$ $f$ $\gamma$ $t$ $l_{1}$ $l_{2}$ $\sigma$ $\gamma$ ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1))$ $\varepsilon$ $f{\wedge }t$ ${\displaystyle 2(l_{1))$ $l_{2})$

Bizonyítás : Tegyük "sorba" négy VP utasításait: , , , (az inverzeket az 1. lemma alapján építjük fel). Ha az egyik vagy mindkét függvény 0-t ad vissza, akkor egy nagy program eredménye : például -val . Ha mindkét függvény 1-et ad vissza, akkor . Itt , ami annak köszönhető, hogy ezek a permutációk 5-ciklikusak ( a szimmetriacsoport feloldhatatlansága miatt ). Az új VI hosszát definíció szerint számítják ki. $(\gamma -t)$ $(\sigma -f)$ $(\gamma ^{-1}-t)$ $(\sigma ^{-1}-f)$ $\varepsilon =id$ $f=0,t=1,\varepsilon =id{\sigma }id{\sigma }^{-1}=id$ ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1))$ $\gamma \sigma \gamma ^{-1}\sigma ^{-1}\neq id<=>\gamma \sigma \neq \sigma \gamma$ $S_{5}$

${\displaystyle}$ A tétel bizonyítása

Indukcióval fogjuk bizonyítani. Tegyük fel, hogy van egy C áramkörünk bemenetekkel , és minden D aláramkörre és 5 ciklusú permutációra van egy VI, amely -kiszámolja D -t . Mutassuk meg, hogy mind az 5-permutációra létezik egy VP, amely -kiszámítja C -t . $x_{1},...,x_{n}$ $\sigma$ $\sigma$ $\sigma$ $\sigma$

Ha a C séma kimenete , akkor a VI-nek egy utasítása van: ellenőrizze az értéket (0 vagy 1), és adja vissza a vagy (illetve) értéket. $x_{i}$ $x_{i}$ $id$ $\sigma$
Ha a C áramkör egy másik A áramkörre A - t állít elő , akkor az 1. lemma megjegyzésével létrehozunk egy VI-t, amely -kiszámítja A -t . $\neg$ $\sigma$ $\neg$
Ha a C áramkör A és B áramkörre A B -t állít elő , akkor a 2. lemma szerint létrehozzuk a kívánt VI-t. $\ék$

A kapott elágazó program mérete nem haladja meg a -t , ahol az áramkör mélysége. Ha a sémának logaritmikus mélysége van, akkor a VP polinomhosszúságú. ${\4. megjelenítési stílus^{d))$ $d$

Jegyzetek

↑ „A szinkron párhuzamos számítások komplexitáselmélete felé. D L'Enseignement mathematique 27” [ eng. ]. Archiválva az eredetiből, ekkor: 2022-03-10 . Letöltve: 2020-04-19 . Elavult használt paraméter |deadlink=( súgó )
↑ Cook, Stephen A. (1985-01-01). „Problémák taxonómiája gyors párhuzamos algoritmusokkal”. Információ és ellenőrzés . Nemzetközi Konferencia a Számításelmélet alapjairól ]. 64 (1):2-22. DOI : 10.1016/S0019-9958(85)80041-3 . ISSN 0019-9958 .
↑ Pippenger, Nicholas (1979). „Az egyidejű erőforrás-korlátokról” . 20. éves szimpózium a számítástechnika alapjairól ( SFCS 1979 ) ]: 307-311. DOI : 10.1109/SFCS.1979.29 . ISSN 0272-5428 .
↑ Arora és Barak (2009) 120. o
↑ 1 2 3 Arora & Barak (2009) 118. o
↑ Papadimitriou (1994) 16.1. Tétel
↑ 1 2 Clote & Kranakis (2002) 437. o
↑ Clote & Kranakis (2002) 12. o
↑ S. Bellantoni és I. Oitavem (2004). „NC elválasztása a delta tengely mentén”. Elméleti számítástechnika . 318 (1-2): 57-78. DOI : 10.1016/j.tcs.2003.10.021 .
↑ 1 2 Clote & Kranakis (2002) 50. o
↑ Barrington, David A. (1989). „A korlátos szélességű polinom méretű elágazó programok pontosan azokat a nyelveket ismerik fel az NC 1 -ben ” (PDF) . J Számítógép. Syst. Sci . 38 (1): 150-164. DOI : 10.1016/0022-0000(89)90037-8 . ISSN 0022-0000 . Zbl 0667.68059 .

Linkek

Arora, Sanjeev. Számítási komplexitás. Modern megközelítés / Sanjeev Arora, Boaz Barak. - Cambridge University Press , 2009. - ISBN 978-0-521-42426-4 .
Clote, Péter. Boole-függvények és számítási modellek / Peter Clote, Evangelos Kranakis. - Berlin: Springer-Verlag , 2002. - ISBN 3-540-59436-1 .
Greenlaw, Raymond, James Hoover és Walter Ruzzo. Határértékek a párhuzamos számításokhoz; P-teljesség elmélet . Archiválva : 2013. június 4. a Wayback Machine ISBN -száma: 0-19-508591-4
Kozen, Dexter C. Algoritmusok tervezése és elemzése. — 1992. 28. — 34. és 36. előadás
Kozen, Dexter C. Számításelmélet. - Springer-Verlag , 2006. - ISBN 1-84628-297-7 . 12. előadás: AzNCaz idő-tér osztályokkal
Papadimitriou, Christos. 15.3. szakasz: Az NC osztály // Számítási komplexitás . — 1. - Addison Wesley, 1993. - P. 375-381 . — ISBN 0-201-53082-1 .
Straubing, Howard. Véges automaták, formális logika és áramkör bonyolultsága . - Bázel: Birkhäuser, 1994. - ISBN 3-7643-3719-2 .
Vollmer, Heribert. Bevezetés az áramkör bonyolultságába. Egységes megközelítés. - Berlin: Springer-Verlag , 1998. - ISBN 3-540-64310-9 .

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES