NC klasse

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 31. maj 2020; checks kræver 8 redigeringer .

I teorien om beregningsmæssig kompleksitet er NC-klassen (fra det engelske Nick's Class ) det sæt af løselighedsproblemer, der kan løses i polylogaritmisk tid på en parallel computer med et polynomielt antal processorer. Med andre ord hører et problem til NC-klassen, hvis der er konstanter, og sådan at det kan løses i tide ved hjælp af parallelle processorer. Stephen Cook [1] [2] opkaldte den "Nick's Class" efter Nick Pippenger , som lavede omfattende forskning [3] i kredsløb med polylogdybde og polynomisk størrelse. [fire] $k$ $c$ $O(\log ^{c}n)$ $O(n^{k})$

Ligesom klassen P kan opfattes som en klasse af formbare problemer ( Cobham's Thesis ), så kan NC opfattes som en klasse af problemer, der effektivt kan løses på en parallel computer. [5] NC er en delmængde af P, fordi parallelle polylogberegninger kan simuleres ved hjælp af sekventielle polynomieberegninger. Det vides ikke, om NP = P er sandt, men de fleste forskere mener, at det ikke er det, hvilket indebærer, at der sandsynligvis er formbare opgaver, der er sekventielle "af natur", og ikke kan accelereres væsentligt ved hjælp af parallelisme. Ligesom klassen af NP-komplette problemer kan opfattes som klassen af "mest sandsynligt uløselige" problemer, så kan klassen af P-komplette problemer , når de reduceres til NC, opfattes som "mest sandsynligt ikke paralleliserbare" eller "sandsynligvis sekventiel af natur".

En parallel computer i definitionen kan betragtes som en parallel random access machine ( PRAM - fra engelsk parallel, random-access machine). Det er en parallel computer med en central hukommelsespool, hvor enhver processor kan få adgang til enhver bit på konstant tid. Definitionen af NC påvirkes ikke af den måde, PRAM får adgang til den samme bit fra flere processorer på samme tid.

NC kan defineres som det sæt af løselighedsproblemer, der kan løses af et distribueret boolesk kredsløb med polylogaritmisk dybde og et polynomielt antal porte .

Opgaver i NC

NC omfatter mange opgaver, herunder:

Addition, multiplikation og division af heltal;
Matrix multiplikation , tælle deres rang, determinant, invers matrix ;
Polynomium gcd ;
At finde den maksimale matchning.

Ofte blev algoritmerne til disse problemer tænkt separat og kunne ikke være en naiv tilpasning af kendte algoritmer - Gauss-metoden og Euklid-algoritmen er afhængig af, at operationer udføres sekventielt.

Hierarki NC

NC i er sættet af løselighedsproblemer, der kan løses af distribuerede booleske kredsløb med et polynomielt antal porte (med ikke mere end to indgange) og dybde , eller som kan løses i tid af en parallel computer med et polynomielt antal processorer. Naturligvis, $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}},

hvad er NC -hierarkiet.

Vi kan forbinde NC -klasserne med lagerklasserne L , NL [6] og AC [7] :

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

Klasserne NC og AC er identisk defineret, bortset fra det ubegrænsede antal ventilindgange for klasse AC. For hver , er [5] [7] sandt : $jeg$

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

En konsekvens af dette er NC = AC . [8] Begge inklusioner er kendt for at være strenge for . [5] På samme måde kan vi få, at NC svarer til det sæt af problemer, der er løst på en variabel Turing-maskine med ikke mere end to valg på hvert trin, og med O (log n ) hukommelse og ændringer. [9] $i=0$ ${\displaystyle (\log n)^{O(1)))$

Uløst problem: er NC native?

Et af de store åbne spørgsmål inden for beregningskompleksitetsteori er, om enhver indlejring af NC-hierarkiet er korrekt. Som bemærket af Papadimitriou, hvis NC i = NC i +1 er sand for nogle , så NC i = NC j for alle , og som en konsekvens, NC i = NC . Denne observation kaldes NC-hierarkifoldning, fordi selv fra en enkelt lighed i redekæden: $jeg$ $j\geqslant i$

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

det følger, at hele NC -hierarkiet "kollapser" til et eller andet niveau . Der er således to muligheder: $jeg$

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

Det er en udbredt opfattelse, at (1) er sandt, selvom der endnu ikke er fundet beviser vedrørende sandheden af nogen af udsagn.

Barringtons sætning

Et forgreningsprogram med variabel, bredde og længde består af en sekvens af længdeinstruktioner . Hver instruktion er en tredobbelt , hvor er indekset for den variabel, der skal kontrolleres , og og er permutationsfunktionerne fra til . Tallene kaldes forgreningsprogrammets tilstande. Programmet starter i tilstand 1, og hver instruktion ændrer tilstanden til eller , afhængigt af om den -th variabel er lig med 0 eller 1. $n$ $k$ $m$ $m$ $(i,p,q)$ $jeg$ $(1\leq i\leq n)$ $s$ $q$ ${\displaystyle \{1,2,...,k\))$ ${\displaystyle \{1,2,...,k\))$ $1,2,...,k$ $(i,p,q)$ $x$ $p(x)$ $q(x)$ $jeg$

Familien af forgreningsprogrammer består af forgreningsprogrammer med variabler for hver . $n$ $n$

Det er let at vise, at ethvert sprog kan genkendes af en familie af forgreningsprogrammer med bredde 5 og eksponentiel længde, eller en familie med eksponentiel bredde og lineær længde. $L$ $\{0,1\}$

Ethvert almindeligt sprog kan ikke genkendes som en familie af lineære instruktions-forgreningsprogrammer med konstant bredde (da en DFA kan konverteres til et forgreningsprogram). BWBP betegner en klasse af sprog, der genkendes af BWBP-familien (afgrænset bredde og polynomielængde) af forgreningsprogrammer . [10] . $\{0,1\}$

Barringtons sætning [11] siger, at BWBP er nøjagtigt ikke-allokeret NC 1 . Beviset for sætningen bruger symmetrigruppens uafgørlighed . [ti] $S_{5}$

Bevis for Barringtons sætning

Lad os bevise, at et forgreningsprogram ( VP ) med konstant bredde og polynomisk størrelse kan omdannes til et kredsløb fra NC 1 .

Tværtimod: lad der være et kredsløb C fra NC 1 . Uden tab af generalitet vil vi antage, at der kun bruges AND og NOT -porte i den.

Definition: En VI kaldes -beregning af en boolsk funktion, eller hvis den giver resultatet - den identiske permutation , og for dens resultat - -permutationen. Da vores C -skema beskriver en boolsk funktion og kun den, kan vi udveksle disse termer. $\sigma$ $f$ $(\sigma -f)$ $f=0$ $f=1$ $\sigma$ $f$

Til beviset vil vi bruge to lemmas:

Lemma 1 : Hvis der er en VP der -beregner , så eksisterer der også en VP der -beregner (det vil sige lig med at og lig med . $\sigma$ $f$ $\sigma ^{-1}$ $f$ $id$ $f=0$ $\sigma ^{-1}$ $f=1$

Bevis : da og er cyklusser, og to cyklusser er konjugeret , så er der en sådan permutation , at = . Derefter gange vi med permutationerne og fra den første VP-instruktion til venstre (for at få permutationerne og ), og gange permutationerne fra den sidste instruktion med højre (vi får og ). Hvis før vores handlinger (uden tab af almenhed) var lig med , så vil resultatet nu være , og hvis det var lig med , så er resultatet lig med . Så vi fik en VI, der -beregner , med samme længde (antallet af instruktioner er ikke ændret). $\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$

Bemærk : hvis vi multiplicerer output fra VP med højre, så får vi på en indlysende måde VP, -beregningsfunktionen . $(\sigma ^{-1}-f)$ $\sigma$ $\sigma$ ${\neg }f$

Lemma 2 : Hvis der er to VI'er: -beregning og -beregning med længder og , hvor og er 5-cykliske permutationer, så eksisterer der en VI med en 5-cyklisk permutation , sådan at VI -beregner , og dens størrelse ikke overstiger + . $\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})$

Bevis : Lad os lægge instruktionerne fra fire VP'er "på række": , , , (vi bygger de omvendte af Lemma 1). Hvis en eller begge funktioner returnerer 0, så er resultatet af et stort program : for eksempel med . Hvis begge funktioner returnerer 1, så . Her , hvilket er sandt på grund af det faktum, at disse permutationer er 5-cykliske (på grund af symmetrigruppens uopløselighed ). Længden af den nye VI beregnes per definition. $(\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}$ Bevis for sætningen

Vi vil bevise ved induktion. Antag, at vi har et kredsløb C med indgange, og at der for alle underkredsløb D og 5-cyklus permutationer er en VI, der -beregner D . Lad os vise, at der for alle 5-permutationer eksisterer en VP, der -beregner C . $x_{1},...,x_{n}$ $\sigma$ $\sigma$ $\sigma$ $\sigma$

Hvis skema C udsender , så har VI en instruktion: Kontroller værdien (0 eller 1), og returner eller (henholdsvis). $x_{i}$ $x_{i}$ $id$ $\sigma$
Hvis kredsløb C producerer A for et andet kredsløb A , skaber vi ved noten til Lemma 1 en VI, der -beregner A . $\neg$ $\sigma$ $\neg$
Hvis kredsløb C producerer A B for kredsløb A og B , vil vi skabe den ønskede VI ifølge Lemma 2. $\kile$

Størrelsen af det resulterende forgreningsprogram overstiger ikke , hvor er kredsløbets dybde. Hvis skemaet har en logaritmisk dybde, så har VP en polynomiel længde. ${\displaystyle 4^{d))$ $d$

Noter

↑ "Mod en kompleksitetsteori om synkron parallel beregning. D L'Enseignement mathematique 27” [ eng. ]. Arkiveret fra originalen 2022-03-10 . Hentet 2020-04-19 . Forældet parameter brugt |deadlink=( hjælp )
↑ Cook, Stephen A. (1985-01-01). "En taksonomi af problemer med hurtige parallelle algoritmer". Information og kontrol . International konference om grundlaget for beregningsteori ]. 64 (1):2-22. DOI : 10.1016/S0019-9958(85)80041-3 . ISSN 0019-9958 .
↑ Pippenger, Nicholas (1979). "På samtidige ressourcegrænser" . 20. årlige symposium om grundlaget for datalogi ( 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) Sætning 16.1
↑ 1 2 Clote & Kranakis (2002) s.437
↑ Clote & Kranakis (2002) s.12
↑ S. Bellantoni og I. Oitavem (2004). "Adskillelse af NC langs deltaaksen". Teoretisk datalogi . 318 (1-2): 57-78. DOI : 10.1016/j.tcs.2003.10.021 .
↑ 1 2 Clote & Kranakis (2002) s.50
↑ Barrington, David A. (1989). "Forgreningsprogrammer i polynomisk størrelse med afgrænset bredde genkender nøjagtigt disse sprog i NC 1 " (PDF) . J Comput. Syst. Sci . 38 (1): 150-164. DOI : 10.1016/0022-0000(89)90037-8 . ISSN 0022-0000 . Zbl 0667.68059 .

Links

Arora, Sanjeev. Beregningsmæssig kompleksitet. En moderne tilgang / Sanjeev Arora, Boaz Barak. - Cambridge University Press , 2009. - ISBN 978-0-521-42426-4 .
Clote, Peter. Booleske funktioner og beregningsmodeller / Peter Clote, Evangelos Kranakis. - Berlin: Springer-Verlag , 2002. - ISBN 3-540-59436-1 .
Greenlaw, Raymond, James Hoover og Walter Ruzzo. Grænser for parallel beregning; P-fuldstændighedsteori . Arkiveret 4. juni 2013 på Wayback Machine ISBN 0-19-508591-4
Kozen, Dexter C. Design og analyse af algoritmer. — 1992. Forelæsninger 28 — 34 og 36
Kozen, Dexter C. Theory of Computation. - Springer-Verlag , 2006. - ISBN 1-84628-297-7 . Forelæsning 12: Relation afNCtil Time-Space-klasser
Papadimitriou, Christos. Afsnit 15.3: Klassen NC // Computational Complexity . — 1. — Addison Wesley, 1993. — S. 375–381 . — ISBN 0-201-53082-1 .
Straubing, Howard. Finite automater, formel logik og kredsløbskompleksitet . - Basel: Birkhäuser, 1994. - ISBN 3-7643-3719-2 .
Vollmer, Heribert. Introduktion til kredsløbskompleksitet. En ensartet tilgang. - Berlin: Springer-Verlag , 1998. - ISBN 3-540-64310-9 .

Kompleksitetsklasser af algoritmer
Betragtes som lys	DLOGTIME AC 0 ACC 0 TC0 [ da L SL RL NL NC SC CC P P-komplet ZPP RP BPP BQP EQP APX
Formodes at være svært	U.P. NP NP komplet co-NP co-NP-komplet AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplet
Anses for vanskelig	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-komplet ALLE