Třídy složitosti a Turingovy stroje

Algoritmy lze rozdělit do několika tříd složitosti na základě času a paměti, jež potřebují ke svému vykonání na různých typech Turingových strojů. Tříd složitosti existují stovky, tento článek představuje ty základní.

Turingův stroj

Turingův stroj je teoretický model počítače, který se skládá z nekonečné pásky rozdělené do buněk, řídící jednotky, která se může nacházet v konečně mnoha stavech a hlavy, která čte a přepisuje jednotlivé záznamy.

Formální popis

Formálně lze popsat Turingův stroj jako sedmici $(Q,\\; \\Sigma,\\; \\Gamma,\\; \\delta,\\; q_{0},\\; B,\\; F)$ , kde je konečná množina stavů, $\\Sigma$ je konečná množina vstupních symbolů, $\\Gamma$ je konečná množina páskových symbolu ( $\\Sigma \\subseteq \\Gamma$ ), $\\delta$ je přechodová funkce, $q_{0}$ je počáteční stav, je blank a je konečná množina koncových stavů.

Počáteční situace a krok Turingova stroje

V počáteční situaci (před započnutím algoritmu) je na pásce umístěn v prvních n buňkách vstup algoritmu, zbytek pásky je vyplněn prázným symbolem B (blank). Hlava ukazuje na první buňku vstupu a řídící jednotka je v počátečním stavu.

Nyní Turingův stroj přečte první buňku, řekněme symbol X a na základě přechodové funkce přejde do následujícího stavu (p), přepíše tuto buňku symbolem daným touto funkcí (Y) a posune se o jedno místo na pásce (vlevo (L) nebo vpravo (R) dle přechodové funkce). Tato akce se zapisuje jako:

$\\delta(q_{0},\\; X) \\rightarrow (p,\\; Y,\\; R)$

Řídící jednotka může zůstat ve svém původním stavu, což v automatu odpovídá smyčce. Pokud to povolíme, tak také hlava může zůstat na stejné pozici. Za předpokladu, že pro daný stav automatu neexistuje přechod, tak Turingův stroj havaruje (skončí neúspěchem). Výpočet končí úspěšně, když řídící jednotka přejde do konečného stavu. Symboly na pásce jsou výstupem algoritmu.

Příklad

Zkonstruujte Turingův stroj, který přijme slovo $w \\in \\{0,\\; 1\\}^{+}$ a na výstupu bude mít slovo wcw .

Interpretace

Turingův stroj začíná ve stavu , jeho hlava čte první symbol. Pokud je tímto symbolem , tak jej přepíše na a přejde do stavu , pokud je čteným symbolem , tak jej přepíše na a přejde do stavu . Jednotlivé větve slouží jako pamět, do které stroj "ukládá" symbol, který má zapsat.

Ve stavech stroj přeiteruje všechny zbylé vstupní symboly. V okamžiku, kdy narazí na blank, tak jej přepíše oddělovacím symbolem a přejde do jednoho ze stavů . Dále podle toho, ve které je větvi, zapíše na konec pásky odpovídající "uložený" symbol, posune se doleva a přejde do stavu .

Nyní se stroj znovu přesune doleva přes uložený oddělovač a přejde do stavu , ve kterém přeiteruje na poslední zpracovaný znak vstupního slova (ten je nyní nebo ). Až tento znak nalezne, tak se pohne doprava, kde vybere první nepracovaný znak, přepíše jej na nebo (stav ) a analogicky s první částí stroje jej zapíše na první volnou pozici vpravo (první blank) - stavy , . Poté se stroj vrátí na první nepřenesený znak prvního slova (smyčka ve stavu , přechod do ).

V okamžiku, kdy jsou již všechny znaky přeneseny, zbývá pouze projít vstupní slovo (nyní složené ze symbolů a ) a převést jej zpět na posloupnost znaků a . Až stroj narazí na první blank vlevo, bude páska obsahovat zduplikované vstupní slovo oddělené symbolem .

Vícepáskový Turingův stroj

Turingův stroj může mít více než jednu pásku. V tomto případě má také více hlav, z nichž každá snímá odpovídající pásku. Přechodová funkce reaguje na stav Turingova stroje a na k symbolů na jednotlivých páskách. V počátečním stavu jsou všechny hlavy nastaveny na první pole odpovídajících pásek, první páska obsahuje vstupní slovo a blanky, zbylé pásky obsahují pouze blanky. Vícepáskový Turingův stroj je převoditelný na jednopáskový tak, že pokud vícepáskový stroj potřeboval je zpracování vstupu O(n) kroků, tak jednopáskový potřebuje $O(n^{2})$ kroků.

Třída P

Rozhodovací úloha U leží ve třídě P právě tehdy, když existuje Turingův stroj, který rozhodne jazyk $L_{u}$ v polynomiálním čase.

Příklady úloh z třídy P

Nejkratší cesty: Existuje v acyklickém grafu mezi uzly a a b cesta, jejíž délka je nejvýše k?
Minimální kostra: Existuje v grafu kostra, jejíž cena je maximálně rovna k?

Třída NP

Rozhodovací úloha U leží ve třídě NP právě tehdy, když existuje nedeterministický Turingův stroj (tj. Turingův stroj, jehož přechodová funkce umožňuje přejít z jednoho stavu pro daný vstup do více různých stavů), který rozhodne jazyk $L_{u}$ v polynomiálním čase.

Jednodušeji lze říct, že je algoritmus pro RAM v třídě NP, pokud lze jeho výsledek ověřit v polynomiálním čase.

Příklady úloh z třídy NP

K-barevnost: Lze daný graf obarvit maximálně k barvami?
Klikovost grafu: Existuje v grafu klika alespoň o k vrcholech?

Třída co-NP

Jazyk je ve třídě co-NP právě tehdy, když je doplněk tohoto jazyka v třídě NP. Zatímco u NP problémů existuje certifikát pro ANO-instanci, u co-NP úloh lze polynomiálně ověřit pouze NE-instanci.

Příklad úlohy z třídy co-NP

Klikovost grafu (doplněk): Mají všechny kliky v grafu méně než k vrcholů?
- Jazyk obsahuje také všechna slova, která neodpovídají žádnému grafu.

Třída NPC

Úloha U je NP-úplná (NPC, NP-complete), pokud je je ve třídě NP a zárověn platí, že se na ní polynomiálně redukuje každá úloha z třídy NP. NP-úplné úlohy jsou ty „nejobtížnější“ ze všech NP úloh.

Polynomiální redukce

Hierarchie tříd složitosti

Polynomiální redukce úloh je převod instance úlohy $U_{1}$ na instanci úlohy $U_{2}$ takový, že platí:

je ANO-instance $U_{1}$ právě tehdy, když je ANO-instance $U_{2}$ .
Převod má polynomiální složitost.

Fakt, že se polynomiálně redukuje na značíme $V \\triangleleft_{p} W$ . Pokud pro dvě NP úlohy V a W platí, že $V \\triangleleft_{p} W$ , pak také platí:

Pokud je V NP-úplná úloha, pak je také W NP-úplná úloha.
Pokud je W v třídě P, pak je také V v třídě P.

Pokud se dala libovolná NP-úplná úloha řešit v polynomiálním čase, pak by platilo NP = P .

Příklady úloh z třídy NP

Třída co-NPC

Jazyk je ve třídě co-NPC právě tehdy, když je doplněk tohoto jazyka ve třídě NPC.

Příklad úlohy z třídy co-NPC

CNF USAT (doplněk CNF SAT): Je daná CNF formule (v konjunktivním normálním tvaru) nesplnitelná?
- Jazyk kromě nesplnitelých formulí obsahuje také všechna slova, která nejsou formulemi.

Třída NP-hard

O úloze U řekneme, že je NP-obtížná (NP-hard, NP-těžká), pokud se na ní redukuje NP-úplná úloha, ale zároveň nevíme, jestli je v NP. Takováto úloha je minimálně stejně težká jako všechny NP-úplné úlohy.

Třídy PSPACE a NPSPACE

Jazyk L je ve třídě $\\mathcal{P}SPACE$ právě tehdy, když existuje deterministický Turingův stroj, který pracuje s polynomiální paměťovou složitostí (tj. nepoužije žádnou paměťovou buňku na indexu vyšším než p(n) ) a přijímá jazyk L.

Jazyk L je ve třídě $\\mathcal{NP}SPACE$ právě tehdy, když existuje nedeterministický Turingův stroj, který pracuje s polynomiální paměťovou složitostí a přijímá jazyk L.

Bylo dokázáno, že $NP \\subseteq \\mathcal{NP}SPACE$ a dále dle Savitchovy věty platí, že $\\mathcal{P}SPACE = \\mathcal{NP}SPACE$ .

Randomizovaný Turingův stroj

Randomizovaný Turingův stroj obsahuje alespoň dvě pásky. První páska je totožná s běžným Turingovým strojem (v počátečním stavu obsahuje vstup a blanky). Druhá páska obsahuje náhodně rozmístěné nuly a jedničky (0 s pravděpodobností 50%, 1 s pravděpodobností 50%). Na tuto pásku nelze zapisovat.

Třída RP

Jazyk L patří do třídy RP (randomizovaně polynomiální) právě tehdy, když existuje randomizovaný Turingův stroj M takový, že:

Pokud $w \\not\\in L$ , tak M skončí v koncovém stavu s pravděpodobností .
Pokud $w \\in L$ , tak M skončí v koncovém stavu s pravděpodobností $\\geq 0.5$ .
Pro každé w ( $\\vert w \\vert = n$ ) potřebuje nejvýše kroků.