NC luokka

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 31.5.2020 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Laskennallisen monimutkaisuuden teoriassa NC-luokka ( englanninkielisestä Nick's Class ) on joukko ratkaistavuusongelmia , jotka voidaan ratkaista polylogaritmisessa ajassa rinnakkaistietokoneella , jossa on polynomimäärä prosessoreita. Toisin sanoen ongelma kuuluu NC-luokkaan, jos siinä on vakioita ja sellaisia, että se voidaan ratkaista ajoissa rinnakkaisilla prosessoreilla. Stephen Cook [1] [2] antoi sille nimen "Nick's Class" Nick Pippengerin mukaan, joka teki laajan tutkimuksen [3] piireistä, joissa on polylogin syvyys ja polynomikoko. [neljä] $k$ $c$ $O(\log ^{c}n)$ $O(n^{k})$

Aivan kuten luokkaa P voidaan pitää muokattavien ongelmien luokkana ( Cobhamin opinnäytetyö ), NC voidaan ajatella luokan tehtävien luokkana, joka voidaan ratkaista tehokkaasti rinnakkaistietokoneella. [5] NC on P:n osajoukko, koska rinnakkaisia polylogialaskuja voidaan simuloida käyttämällä peräkkäisiä polynomialaskuja. Ei tiedetä, onko NP = P totta, mutta useimmat tutkijat uskovat, että se ei pidä paikkaansa, mikä tarkoittaa, että on todennäköisesti muovattavia tehtäviä, jotka ovat "luonnoltaan" peräkkäisiä ja joita ei voida merkittävästi nopeuttaa rinnakkaisuuden avulla. Aivan kuten NP-täydellisten ongelmien luokkaa voidaan pitää "todennäköisimmin ratkaisemattomien" ongelmien luokkana, niin P-täydellisten ongelmien luokkaa , kun se pelkistetään NC:ksi, voidaan ajatella "todennäköisimmin ei rinnakkaistavissa" tai "todennäköisimmin peräkkäinen luonteeltaan".

Määritelmässä olevaa rinnakkaistietokonetta voidaan pitää rinnakkaisena hajasaantikoneena ( PRAM - englannin kielestä rinnakkais, random-access machine). Se on rinnakkaistietokone, jossa on keskusmuisti, jonka mikä tahansa prosessori voi käyttää mitä tahansa bittiä vakioajassa. NC:n määritelmään ei vaikuta tapa, jolla PRAM käyttää samaa bittiä useista prosessoreista samanaikaisesti.

NC voidaan määritellä joukkona ratkaistavuusongelmia, jotka voidaan ratkaista hajautetulla Boolen piirillä , jolla on polylogaritminen syvyys ja polynomimäärä portteja .

Tehtävät NC:ssä

NC sisältää monia tehtäviä, mukaan lukien:

Kokonaislukujen yhteen-, kerto- ja jakolasku;
Matriisin kertolasku , niiden järjestyksen laskeminen, determinantti, käänteimatriisi ;
polynomi gcd ;
Maksimiyhteensopivuuden löytäminen.

Usein näiden ongelmien algoritmit keksittiin erikseen, eivätkä ne voineet olla tunnettujen algoritmien naiivia adaptaatiota - Gaussin menetelmä ja Euclid-algoritmi perustuvat siihen, että toiminnot suoritetaan peräkkäin.

Hierarkia NC

NC i on joukko ratkeavuusongelmia, jotka voidaan ratkaista hajautetuilla Boolen piireillä, joissa on polynomimäärä portteja (enintään kaksi tuloa) ja syvyys , tai jotka voidaan ratkaista ajallisesti rinnakkaistietokoneella, jossa on polynomimäärä prosessoreita. Ilmeisesti $O(\log ^{i}n)$ $O(\log ^{i}n)$

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

mikä on NC - hierarkia.

Voimme yhdistää NC -luokat tallennusluokkiin L , NL [6] ja AC [7] :

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

Luokat NC ja AC ovat identtisiä, lukuun ottamatta rajatonta määrää venttiilituloja luokassa AC. Jokaisen kohdalla [5] [7] on totta : $i$

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

Tämän seurauksena NC = AC . [8] Molempien sisällytysten tiedetään olevan tiukkoja . [5] Vastaavasti voimme saada, että NC vastaa muuttujalla Turingin koneella ratkaistavia tehtäviä, joissa on enintään kaksi vaihtoehtoa kussakin vaiheessa ja O (log n ) muistilla ja muutoksilla. [9] $i = 0$ ${\displaystyle (\log n)^{O(1)))$

Ratkaisematon ongelma: onko NC natiivi?

Yksi laskennan monimutkaisuusteorian suurista avoimista kysymyksistä on, onko jokainen NC-hierarkian upotus oikein. Kuten Papadimitriou huomautti, jos NC i = NC i +1 on totta joillekin , niin NC i = NC j kaikille , ja sen seurauksena NC i = NC . Tätä havaintoa kutsutaan NC-hierarkian taitoksi, koska jopa yhdestä tasa-arvosta sisäkkäisketjussa: $i$ $j\geqslant i$

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

tästä seuraa, että koko NC -hierarkia "lupautuu" jollekin tasolle . Näin ollen kaksi vaihtoehtoa on mahdollista: $i$

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

Yleisesti uskotaan, että (1) on totta, vaikka todisteita kummankaan väitteen totuudesta ei ole vielä löydetty.

Barringtonin lause

Muuttujien, leveyden ja pituuden haaroitusohjelma koostuu joukosta pituuskäskyjä . Jokainen käsky on kolmiosainen , jossa on tarkistettavan muuttujan indeksi ja ja ovat permutaatiofunktiot alkaen - . Numeroita kutsutaan haarautumisohjelman tiloiksi. Ohjelma alkaa tilasta 1, ja jokainen käsky muuttaa tilan tai -tilaan riippuen siitä, onko -: s muuttuja 0 vai 1. $n$ $k$ $m$ $m$ ${\näyttötyyli (i,p,q)}$ $i$ $(1\leq i\leq n)$ $s$ $q$ $\{1,2,...,k\}$ $\{1,2,...,k\}$ ${\näyttötyyli 1,2,...,k}$ ${\näyttötyyli (i,p,q)}$ $x$ $p(x)$ $q(x)$ $i$

Haaroitusohjelmien perhe koostuu haaroitusohjelmista, joissa jokaiselle on muuttuja . $n$ $n$

On helppo osoittaa, että mikä tahansa kieli voidaan tunnistaa haarautuvien ohjelmien perheestä, jonka leveys on 5 ja pituus eksponentiaalinen, tai perheestä, jonka leveys ja lineaarinen pituus on eksponentiaalinen. $L$ $\{0,1\}$

Jokaista säännöllistä kieltä ei voida tunnistaa vakioleveyksisten, lineaarista käskyä haaroittavien ohjelmien perheeksi (koska DFA voidaan muuntaa haarautumisohjelmaksi). BWBP tarkoittaa kieliluokkaa, jonka tunnistaa BWBP (rajoitettu leveys ja polynomipituus) haarautuvien ohjelmien perhe . [10] . $\{0,1\}$

Barringtonin lause [11] väittää, että BWBP on täsmälleen allokoimaton NC 1 . Lauseen todistuksessa käytetään symmetriaryhmän ratkaisemattomuutta . [kymmenen] $S_{5}$

Todistus Barringtonin lauseesta

Osoitetaan, että haaroitusohjelma ( VP ), jolla on vakioleveys ja polynomikoko, voidaan muuttaa piiriksi NC 1 :stä .

Päinvastoin: olkoon piiri C NC 1 :stä . Yleisyyttä menettämättä oletetaan, että siinä käytetään vain AND- ja EI - portteja .

Määritelmä: VI:tä kutsutaan Boolen funktion -laskemiseksi tai jos se antaa tuloksen - identtisen permutaation ja sen tulokseksi -permutaatioksi. Koska C -skeemamme kuvaa jotain Boolen funktiota ja vain sitä, voimme vaihtaa nämä termit keskenään. $\sigma$ $f$ $(\sigma -f)$ $f=0$ $f=1$ $\sigma$ $f$

Todistuksessa käytämme kahta lemmaa:

Lemma 1 : Jos on VP, joka -laskee , niin on olemassa myös VP, joka -laskee (eli yhtä suuri kuin , ja yhtä suuri kuin . $\sigma$ $f$ $\sigma ^{-1}$ $f$ $id$ $f=0$ $\sigma ^{-1}$ $f=1$

Todistus : koska ja ovat jaksoja ja mitkä tahansa kaksi sykliä ovat konjugoituja , niin on olemassa sellainen permutaatio , että = . Sitten kerrotaan permutaatioilla ja ensimmäisestä vasemmanpuoleisesta VP-käskystä (jotta saadaan permutaatiot ja ), ja kerrotaan permutaatiot viimeisestä käskystä oikealla (saamme ja ). Jos ennen toimintamme (ilman yleisyyden menetystä) oli yhtä suuri kuin , niin nyt tulos on , ja jos se oli yhtä suuri , tulos on yhtä suuri kuin . Saimme siis VI:n, joka -laskee , samanpituisena (käskyjen määrä ei ole muuttunut). $\sigma$ $\sigma ^{-1}$ $\pi$ $\sigma ^{-1}$ ${\displaystyle \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$

Huomaa : jos kerromme VP : n ulostulon oikealla, niin saadaan ilmeisellä tavalla VP, -laskentafunktio . $(\sigma ^{-1}-f)$ $\sigma$ $\sigma$ ${\neg }f$

Lemma 2 : Jos on kaksi VI:tä: -laskeminen ja -laskenta pituuksilla ja , missä ja ovat 5-syklisiä permutaatioita, niin on olemassa VI, jolla on 5-syklinen permutaatio siten, että VI -laskee ja sen koko ei ylitä + . $\sigma$ $f$ $\gamma$ $t$ $l_{1}$ $l_{2}$ $\sigma$ $\gamma$ ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1))$ $\varepsilon$ $f{\wedge }t$ ${\näyttötyyli 2(l_{1))$ $l_{2})$

Todistus : Laitetaan "peräkkäin" neljän VP:n ohjeet: , , , (käänteiset rakennamme Lemman 1 mukaan). Jos toinen tai molemmat funktiot palauttavat arvon 0, niin suuren ohjelman tulos on : esimerkiksi . Jos molemmat funktiot palauttavat arvon 1, niin . Tässä , mikä on totta, koska nämä permutaatiot ovat 5-syklisiä ( symmetriaryhmän ratkaisemattomuudesta johtuen ). Uuden VI:n pituus lasketaan määritelmän mukaan. ${\näyttötyyli (\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}$ Todistus lauseesta

Todistamme induktiolla. Oletetaan, että meillä on piiri C tuloineen ja että kaikille alipiireille D ja 5-jaksoisille permutaatioille on VI, joka -laskee D :n . Osoitetaan, että kaikille 5-permutaatioille on olemassa VP, joka -laskee C :n . $x_{1},...,x_{n}$ $\sigma$ $\sigma$ $\sigma$ $\sigma$

Jos skeema C tulostaa , VI:ssä on yksi käsky: tarkista arvo (0 tai 1) ja palauta tai (vastaavasti). $x_{i}$ $x_{i}$ $id$ $\sigma$
Jos piiri C tuottaa A :n jollekin toiselle piirille A , luomme Lemmaan 1 huomautuksella VI, joka -laskee A:n . $\neg$ $\sigma$ $\neg$
Jos piiri C tuottaa A B :n piireille A ja B , luomme halutun VI:n Lemman 2 mukaisesti. $\kiila$

Tuloksena olevan haaroitusohjelman koko ei ylitä , missä on piirin syvyys. Jos kaaviolla on logaritminen syvyys, niin VP:llä on polynomipituus. ${\näyttötyyli 4^{d))$ $d$

Muistiinpanot

↑ "Kohti synkronisen rinnakkaislaskennan kompleksisuusteoriaa. D L'Enseignement mathematique 27” [ eng. ]. Arkistoitu alkuperäisestä 2022-03-10 . Haettu 19.04.2020 . Käytöstä poistettu parametri |deadlink=( ohje )
↑ Cook, Stephen A. (1985-01-01). "Nopeiden rinnakkaisten algoritmien ongelmien taksonomia". Tiedot ja valvonta . Kansainvälinen konferenssi laskennan teorian perusteista ]. 64 (1):2-22. DOI : 10.1016/S0019-9958(85)80041-3 . ISSN 0019-9958 .
↑ Pippenger, Nicholas (1979). "Samanaikaisilla resurssirajoilla" . 20th Annual Symposium on Foundations of Computer Science ( SFCS 1979 ) ]: 307-311. DOI : 10.1109/SFCS.1979.29 . ISSN 0272-5428 .
↑ Arora & Barak (2009) s. 120
↑ 1 2 3 Arora & Barak (2009) s. 118
↑ Papadimitriou (1994) Lause 16.1
↑ 1 2 Clote & Kranakis (2002) s. 437
↑ Clote & Kranakis (2002) s. 12
↑ S. Bellantoni ja I. Oitavem (2004). "NC:n erottaminen delta-akselia pitkin". Teoreettinen tietojenkäsittelytiede . 318 (1-2): 57-78. DOI : 10.1016/j.tcs.2003.10.021 .
↑ 1 2 Clote & Kranakis (2002) s. 50
↑ Barrington, David A. (1989). "Rajaleveät polynomikokoiset haarautumisohjelmat tunnistavat juuri ne kielet NC 1 :ssä " (PDF) . J Comput. Syst. Sci . 38 (1): 150-164. DOI : 10.1016/0022-0000(89)90037-8 . ISSN 0022-0000 . Zbl 0667.68059 .

Linkit

Arora, Sanjeev. Laskennallinen monimutkaisuus. Moderni lähestymistapa / Sanjeev Arora, Boaz Barak. - Cambridge University Press , 2009. - ISBN 978-0-521-42426-4 .
Clote, Peter. Boolen funktiot ja laskentamallit / Peter Clote, Evangelos Kranakis. - Berliini: Springer-Verlag , 2002. - ISBN 3-540-59436-1 .
Greenlaw, Raymond, James Hoover ja Walter Ruzzo. Limits To Parallel Computation; P-täydellisyyden teoria . Arkistoitu 4. kesäkuuta 2013 Wayback Machinessa ISBN 0-19-508591-4
Kozen, Dexter C. Algoritmien suunnittelu ja analyysi. - 1992. Luennot 28 - 34 ja 36
Kozen, Dexter C. Laskennan teoria. - Springer-Verlag , 2006. - ISBN 1-84628-297-7 . Luento 12:NCaika-avaruusluokkiin
Papadimitriou, Christos. Osa 15.3: Luokka NC // Laskennallinen monimutkaisuus . – 1. - Addison Wesley, 1993. - S. 375-381 . — ISBN 0-201-53082-1 .
Straubing, Howard. Äärilliset automaatit, muodollinen logiikka ja piirin monimutkaisuus . - Basel: Birkhäuser, 1994. - ISBN 3-7643-3719-2 .
Vollmer, Heribert. Johdatus piirin monimutkaisuuteen. Yhtenäinen lähestymistapa. - Berliini: Springer-Verlag , 1998. - ISBN 3-540-64310-9 .

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI