NC (složitost) - NC (complexity)

Question, Web Fundamentals.svgNevyřešený problém v informatice:
(více nevyřešených problémů v informatice)

v teorie výpočetní složitosti, třída NC (pro „Nickovu třídu“) je sada rozhodovací problémy rozhodnutelný v polylogaritmický čas na paralelní počítač s polynomickým počtem procesorů. Jinými slovy, problém je v NC pokud existují konstanty C a k tak, aby to bylo možné včas vyřešit Ó (logC n) použitím Ó (nk) paralelní procesory. Stephen Cook[1][2] vymyslel název „Nickova třída“ Nick Pippenger, který provedl rozsáhlý výzkum[3] na obvodech s polylogaritmickou hloubkou a velikostí polynomu.[4]

Stejně jako třída P lze považovat za potížné problémy (Cobhamova teze ), tak NC lze považovat za problémy, které lze efektivně vyřešit na paralelním počítači.[5] NC je podmnožinou P protože polylogaritmické paralelní výpočty lze simulovat polynomiálně-časově sekvenčními. Není známo, zda NC = P, ale většina vědců má podezření, že je to nepravdivé, což znamená, že pravděpodobně existují nějaké problémy, které lze vyřešit, které jsou „neodmyslitelně sekvenční“ a nelze je významně urychlit použitím paralelismu. Stejně jako třída NP-kompletní lze považovat za „pravděpodobně neřešitelný“, takže třída P-kompletní, při použití NC redukce, lze považovat za „pravděpodobně ne paralelizovatelné“ nebo „pravděpodobně neodmyslitelně sekvenční“.

Lze předpokládat, že paralelní počítač v definici je a paralelní stroj s náhodným přístupem (PRAM ). Jedná se o paralelní počítač s centrálním fondem paměti a jakýkoli procesor může přistupovat k libovolnému kousku paměti v konstantním čase. Definice NC není ovlivněna volbou způsobu, jakým PRAM zpracovává současný přístup k jednomu bitu více než jedním procesorem. Může to být CRCW, CREW nebo EREW. Vidět PRAM pro popis těchto modelů.

Ekvivalentně NC lze definovat jako ty problémy s rozhodováním, o kterých lze rozhodnout a jednotný booleovský obvod (což lze vypočítat z délky vstupu, pro NC předpokládáme, že můžeme vypočítat booleovský obvod velikosti n v logaritmickém prostoru v n) s polylogaritmický hloubka a polynomiální počet bran.

RNC je rozšiřující třída NC s přístupem k náhodnosti.

Problémy v NC

Stejně jako u P, mírným zneužitím jazyka by se dalo klasifikovat funkční problémy a problémy s vyhledáváním jako v NC. NC je známo, že zahrnuje mnoho problémů, včetně

Algoritmy pro tyto problémy musely být často vynalézány samostatně a nemohly být naivně upraveny ze známých algoritmů - Gaussova eliminace a Euklidovský algoritmus spoléhat se na operace prováděné v pořadí. Jeden by mohl kontrastovat zvlnění nést zmije s carry-lookahead zmije.

Hierarchie NC

NCi je třída rozhodovacích problémů, které lze určit jednotnými booleovskými obvody s polynomiálním počtem bran maximálně dvou vstupů a hloubky Ó(logi n), nebo třída rozhodovacích problémů řešitelných v čase Ó(logi n) na paralelním počítači s polynomickým počtem procesorů. Je zřejmé, že máme

který tvoří NC-hierarchie.

Můžeme uvést do souvislosti NC třídy do vesmírných tříd L a NL[6] a AC.[7]

Třídy NC souvisejí s třídami střídavého proudu, které jsou definovány podobně, ale s branami bez neomezeného vstupu. Pro každého i, my máme[5][7]

Okamžitým důsledkem toho je to NC = AC.[8]Je známo, že obě inkluze jsou přísné pro i = 0.[5]

Podobně to máme NC je ekvivalentní problémům řešitelným na střídavý Turingův stroj omezeno na maximálně dvě možnosti v každém kroku s Ó(log n) prostor a střídání.[9]

Otevřený problém: Je NC správné?

Jedna hlavní otevřená otázka v teorie složitosti je, zda je nebo není každé zadržení v NC hierarchie je správná. Papadimitriou bylo zjištěno, že pokud NCi = NCi+1 pro některé i, pak NCi = NCj pro všechny j ≥ i, a jako výsledek, NCi = NC. Toto pozorování je známé jako NC-hierarchie se zhroutí, protože dokonce jediná rovnost v řetězci kontejnmentů

znamená, že celý NC hierarchie se „zhroutí“ na určitou úroveň i. Existují tedy 2 možnosti:

Obecně se věří, že tomu tak je (1), ačkoli dosud nebyl objeven žádný důkaz o pravdivosti kteréhokoli z těchto tvrzení.

NC0

Speciální třída NC0 pracuje pouze na konstantní délce vstupních bitů. Proto je popsána jako třída funkcí definovatelných jednotnými booleovskými obvody s konstantní hloubkou a omezeným fanoutem.

Barringtonova věta

A větvící program s n proměnné šířky k a délka m se skládá ze sekvence m instrukce. Každá z pokynů je n-ticí (i, p, q) kde i je index proměnné ke kontrole (1 ≤ i ≤ n), a p a q jsou funkce od {1, 2, ..., k} až {1, 2, ..., k}. Čísla 1, 2, ..., k se nazývají stavy rozvětvovacího programu. Program nejprve začíná ve stavu 1 a každá instrukce (i, p, q) změní stav z X na p(X) nebo q(X), v závislosti na tom, zda ith proměnná je 0 nebo 1.

Rodina programů větvení se skládá z programu větvení s n proměnné pro každou n.

Je snadné ukázat, že každý jazyk L na {0,1} lze rozpoznat podle rodiny větvících programů o šířce 5 a exponenciální délce, nebo podle rodiny exponenciální šířky a lineární délky.

Každý běžný jazyk na {0,1} lze rozpoznat pomocí rodiny větvících programů s konstantní šířkou a lineárním počtem instrukcí (protože DFA lze převést na větvicí program). BWBP označuje třídu jazyků rozpoznatelných rodinou větvících programů s omezenou šířkou a délkou polynomu.[10]

Barringtonova věta[11] říká to BWBP je přesně nejednotný NC1. Důkaz používá neřešitelnost symetrické skupiny S5.[10]

Věta je docela překvapivá. Například to znamená, že většinová funkce lze vypočítat pomocí rodiny větvících se programů s konstantní šířkou a velikostí polynomu, zatímco intuice může naznačovat, že k dosažení velikosti polynomu je potřeba lineární počet stavů.

Důkaz Barringtonovy věty

Rozvětvovací program s konstantní šířkou a velikostí polynomu lze snadno převést (pomocí divide-and-conquer) na obvod v NC1.

Naopak předpokládejme obvod NC1 je dáno. Bez ztráty obecnosti předpokládejme, že používá pouze brány AND a NOT.

Lemma 1: Pokud existuje program větvení, který někdy funguje jako permutace P a někdy jako obměna Q, vynásobením pravých permutací v první instrukci α a v poslední instrukci vynásobením β můžeme vytvořit obvod stejné délky, který se chová jako βPα nebo βQα.

Zavolejte větvící program α-výpočet obvodu C pokud funguje jako identita, když je výstup C 0, a jako α, když je výstup C 1.

V důsledku Lemmy 1 a skutečnosti, že všechny cykly délky 5 jsou sdružené, pro libovolné dva 5 cykly α, β, pokud existuje program větvení α-výpočet obvodu C, pak existuje větvící program β-výpočet obvodu Cstejné délky.

Lema 2: Existuje 5 cyklů γ, δ takových, že jejich komutátor ε = γδγ−1δ−1 je 5-cyklus. Například γ = (1 2 3 4 5), δ = (1 3 5 4 2) dává ε = (1 3 2 5 4).

Nyní ukážeme Barringtonovu větu indukcí:

Předpokládejme, že máme obvod C který přijímá vstupy X1,...,Xn a předpokládejme, že pro všechny dílčí obvody D z C a 5 cyklů α, existuje větvící program α-computing D. Ukážeme, že pro všech 5 cyklů α existuje větvící program α-computing C.

  • Pokud obvod C jednoduše vydá nějaký vstupní bit Xi, program větvení, který potřebujeme, má pouze jednu instrukci: kontrolu Xi'hodnota s (0 nebo 1) a výstup identity nebo α (v uvedeném pořadí).
  • Pokud obvod C výstupy ¬A pro nějaký jiný obvod A, vytvořte větvící program α−1-výpočetní A a poté vynásobte výstup programu hodnotou α. Od Lemmy 1 získáme program větvení pro A výstup identity nebo α, tj. α-výpočet ¬A=C.
  • Pokud obvod C výstupy A∧B pro obvody A a B, připojte se k větvícím programům, které vypočítávají y A, δ-výpočet B, γ−1-vypočítat Aa δ−1-počítat B pro volbu 5-cyklů γ a δ tak, aby jejich komutátor ε = γδγ−1δ−1 je také 5-cyklus. (Existence takových prvků byla stanovena v Lemmě 2.) Pokud jeden nebo oba z výstupů obvodů 0, výsledný program bude identita kvůli zrušení; jsou-li výstupy obou obvodů 1, výsledný program vydá komutátor ε. Jinými slovy, dostaneme program ε-computing A∧B. Protože ε a α jsou dva 5 cykly, jsou konjugované, a proto existuje program α-computing A∧B podle Lemma 1.

Za předpokladu, že dílčí obvody mají větvící se programy, takže jsou α-výpočetní pro všech 5 cyklů α∈S5, ukázali jsme C také má tuto vlastnost, jak je požadováno.

Velikost programu větvení je maximálně 4d, kde d je hloubka obvodu. Pokud má obvod logaritmickou hloubku, má program větvení polynomiální délku.

Poznámky

  1. ^ „Směrem k teorii složitosti synchronního paralelního výpočtu. D L'Enseignement mathematique 27“. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ Cook, Stephen A. (01.01.1985). "Taxonomie problémů s rychlými paralelními algoritmy". Informace a kontrola. Mezinárodní konference o základech teorie výpočtu. 64 (1): 2–22. doi:10.1016 / S0019-9958 (85) 80041-3. ISSN  0019-9958.
  3. ^ Pippenger, Nicholas (1979). „Při současném omezení zdrojů“. 20. výroční sympozium o základech informatiky (SFCS 1979): 307–311. doi:10.1109 / SFCS.1979.29. ISSN  0272-5428.
  4. ^ Arora & Barak (2009), s. 120
  5. ^ A b C Arora & Barak (2009) str.118
  6. ^ Papadimitriou (1994) Věta 16.1
  7. ^ A b Clote & Kranakis (2002), s. 437
  8. ^ Clote & Kranakis (2002) str.12
  9. ^ S. Bellantoni a I. Oitavem (2004). Msgstr "Oddělující NC podél delta osy". Teoretická informatika. 318 (1–2): 57–78. doi:10.1016 / j.tcs.2003.10.021.
  10. ^ A b Clote & Kranakis (2002) str.50
  11. ^ Barrington, David A. (1989). „Rozvětvovací programy s polynomiální velikostí s ohraničenou šířkou přesně rozpoznávají tyto jazyky NC1" (PDF). J. Comput. Syst. Sci. 38 (1): 150–164. doi:10.1016/0022-0000(89)90037-8. ISSN  0022-0000. Zbl  0667.68059.

Reference