AdamátorZápiskyHlášky

Teorie složitosti

Tyto zápisky jsou z přednášek Ing. Petra Ambrože, Ph.D.

Příklad Mějme Turingův stroj 𝒜1 na rozeznávání jazyka
L≔{0n1n|n≥0},
který jsme si sestrojili na JAU. Fungování tohoto stroje sestává z kroků:
  1. Čti vstup a zamítni, pokud najdeš nulu napravo od jedničky (neboli zkontroluj, zda vstup odpovídá regulárnímu výrazu [0*1*]).
  2. Dokud jsou na pásce nuly a jedničky, škrtni jednu nulu a jednu jedničku.
  3. Zkontroluj, jestli na pásce nic nezůstalo.
Zajímalo by nás, jak dlouho stroj poběží v závislosti na délce vstupu.
Definice Nechť 𝒜 je jednopáskový totální deterministický Turingův stroj. Potom časová složitost 𝒜 je funkce f:ℕ→ℕ, která číslu n přiřadí maximální počet kroků výpočtu přes všechny možné vstupy délky n. Říkáme, že 𝒜 počítá v čase f(n).
Definice Nechť f,g:ℕ→ℝ0+. Řekneme, že f je třídy 𝒪(g(n)), pokud existují konstanty c,n0 takové, že pro každé n≥n0 je f(n)≤c⋅g(n), nebo ekvivalentně
lim supn→∞f(n)g(n)<∞.
Píšeme f(n)=𝒪(g(n)), což je trochu nekorektní zápis.
Definice Nechť f,g:ℕ→ℝ0+. Řekneme, že f je třídy ℴ(g(n)), pokud
limn→∞f(n)g(n)=0.
Píšeme f(n)=ℴ(g(n)).
Příklad Časová složitost našeho Turingova stroje je 𝒪(n2), protože při druhém kroku musí n2-krát přeběhnout tam a zpátky.
Příklad K rozeznání jazyka můžeme použít i jiný algoritmus:
  1. Čti vstup a zamítni, pokud najdeš nulu napravo od jedničky.
  2. Dokud jsou na pásce nuly a jedničky, zkontroluj, jestli mají stejnou paritu, následně smaž každou druhou nulu a každou druhou jedničku.
  3. Zkontroluj, jestli na pásce nic nezůstalo.
Tento algoritmus má složitost 𝒪(n⋅logn).
Definice Nechť t:ℕ→ℝ0+. Potom 𝖳𝖨𝖬𝖤(t(n)) je třída všech jazyků, které jsou rozhodnutelné na jednopáskovém deterministickém Turingově stroji v čase 𝒪(t(n)).
Lemma Kobayashi, Hennie Nechť f:ℕ→ℕ je třídy ℴ(n⋅logn). Potom 𝖳𝖨𝖬𝖤(f(n))⊂RecA*.
Příklad Omezení na jednopáskové stroje je důležité. Pokud povolíme dvě pásky, dokážeme sestrojit pro náš jazyk O(n) algoritmus.
  1. Čti vstup a zamítni, pokud najdeš nulu napravo od jedničky.
  2. Překopíruj všechny nuly z první pásky na druhou pásku.
  3. Postupně škrtej jedničky z první pásky a nuly z druhé pásky.
  4. Zkontroluj, jestli na páskách nezůstalo.
Věta Nechť t:ℕ→ℕ je funkce taková, že t(n)≥n. Potom pro každý vícepáskový Turingův stroj se složitostí t(n) existuje jednopáskový Turingův stroj se složitostí 𝒪(t2(n)).
Důkaz Velmi neformálně: Budeme simulovat vícepáskový Turingův stroj pomocí jednopáskového. TBD
Definice Nechť 𝒜 je totální nedeterministický Turingův stroj. Potom jeho časová složitost je funkce f:ℕ→ℕ, která číslu n přiřadí maximální počet kroků v libovolné větvi přes všechny vstupy délky n.
Věta Nechť t:ℕ→ℕ je funkce s t(n)≥n. Potom pro každý jednopáskový nedeterministický Turingův stroj s časovou složitostí t(n) existuje ekvivalentní jednopáskový deterministický Turingův stroj s časovou složitostí 2𝒪(t(n)).
Definice Třída 𝖯 je třída všech jazyků, které jsou na jednopáskovém deterministickém Turingově stroji rozhodnutelné v polynomiálním čase. Jinými slovy:
𝖯=⋃k𝖳𝖨𝖬𝖤(nk).
Poznámka U třídy 𝖯 na rozdíl od tříd 𝖳𝖨𝖬𝖤(t(n)) nezáleží na tom, který model deterministického Turingova stroje používáme.
Poznámka V praxi třída 𝖯 celkem dobře odpovídá třídě problémů, které jdou v rozumném čase řešit na počítači.
Příklad Mějme problém, jestli v orientovaném grafu G existuje cesta mezi vrcholy s,t. Budeme-li analogicky jako v JAU používat špičaté závorky pro nějaké zakódování dat, můžeme formálně uvažovat rozeznávání jazyka
PATH≔{⟨G,s,t⟩|s⇝Gt}.
Tento jazyk je třídy 𝖯, protože můžeme použít například prohledávání do šířky.
Příklad Mějme problém, jestli je dané slovo rozeznávané danou bezkontextovou gramatikou. Gramatiku nejdřív převedeme do Chomského normální formy. Poté můžeme použít dynamický algoritmus, který pro každý podřetězec najde, ze kterých nonterminálů jde vygenerovat. Tento algoritmus bude mít složitost 𝒪(n3), takže problém je v 𝖯.
Definice Turingův stroj 𝒜 je verifikační algoritmus pro jazyk L, pokud L je množina všech slov w takových, že 𝒜 přijme ⟨w,c⟩ pro nějaké c. Slovu c říkáme certifikát.
Definice Třída 𝖭𝖯 je třída všech jazyků, pro které existuje verifikační algoritmus s polynomiální časovou složitostí.
Příklad Problém hledání hamiltonovské cesty v grafu je třídy 𝖭𝖯, protože pokud dostaneme graf a cestu (ta bude náš certifikát), můžeme v polynomiálním čase zjistit, jestli se jedná o hamiltonovskou cestu.
Věta Jazyk je třídy 𝖭𝖯, právě když je přijímaný v polynomiálním čase na nedeterministickém Turingově stroji.
Poznámka Název 𝖭𝖯 je motivovaný právě touto ekvivalentní definicí.
Důkaz
(⇒)
Nechť existuje verifikační algoritmus s polynomiální složitostí p(n). Vezmeme nedeterministický Turingův stroj, který nedeterministicky vybere certifikát délky nanejvýš p(n) a pustí původní Turingův stroj s tímto certifikátem.
(⇐)
Nechť existuje nedeterministický řešící algoritmus. Vezmeme deterministický Turingův stroj, který dostane slovo w a certifikát c, přičemž po certifikátu budeme požadovat, aby nám říkal, jak se v průběhu výpočtu máme nedeterministicky rozhodovat.
Definice Nechť t:ℕ→ℝ0+. Potom 𝖭𝖳𝖨𝖬𝖤(t(n)) je třída všech jazyků, které jsou rozhodnutelné na nedeterministickém Turingově stroji v čase 𝒪(t(n)).
Poznámka
𝖭𝖯=⋃k∈ℕ𝖭𝖳𝖨𝖬𝖤(nk).
Definice Jazyk L patří do třídy 𝖼𝗈𝖭𝖯, pokud L¯ patří do třídy 𝖭𝖯.
Poznámka Zjevně platí 𝖯⊂𝖭𝖯∩𝖼𝗈𝖭𝖯. Ale jinak o třídě 𝖼𝗈𝖭𝖯 skoro nic nevíme, například jestli se rovná 𝖭𝖯 nebo jestli 𝖯=𝖭𝖯∩𝖼𝗈𝖭𝖯.
Definice Definujeme třídu složitosti
𝖤𝖷𝖯𝖳𝖨𝖬𝖤≔⋃k∈ℕ𝖳𝖨𝖬𝖤(2nk).
Poznámka Platí 𝖭𝖯⊂𝖤𝖷𝖯𝖳𝖨𝖬𝖤.
Definice Funkce f:A*→A* je polynomiálně vyčíslitelná, pokud je turingovsky vyčíslitelná Turingovým strojem s polynomiální časovou složitostí.
Definice Jazyk L1∈A* je polynomiálně redukovatelný na jazyk L2∈A*, pokud existuje polynomiálně vyčíslitelná funkce f:A*→A* taková, že ∀w∈A*:w∈L1⟺f(w)∈L2. Značíme L1≤PL2.
Poznámka Pokud L1≤PL2 a L2∈𝖯, potom L1∈𝖯.
Definice Jazyk je 𝖭𝖯-těžký, pokud je na něj každý jazyk z 𝖭𝖯 polynomiálně redukovatelný. Jazyk je 𝖭𝖯-úplný (třídy 𝖭𝖯𝖢), pokud je třídy 𝖭𝖯 a zároveň 𝖭𝖯-těžký.
Důsledek Je-li jazyk L∈𝖭𝖯𝖢∩𝖯, potom 𝖯=𝖭𝖯.
Příklad Příkladem 𝖭𝖯-úplného problému je problém booleovské splnitelnosti (SAT): máme danou výrokovou formuli a chceme zjistit, jestli je splnitelná, tedy jestli existuje nastavení logických proměnných, pro které je složený výrok pravdivý. Snadno dokážeme, že problém patří do 𝖭𝖯 – stačí vzít jako certifikát hodnoty proměnných, pro které je formule splněna. Zbývá dokázat, že je 𝖭𝖯-těžký. K tomu si nejdřív zavedeme několik pojmů.
Definice Literál je booleovská proměnná nebo její negace. Klauzule je několik literálů spojených disjunkcemi. Booleovská formule je v konjunktivní normální formě (CNF), pokud je to několik klauzulí spojených konjunkcemi. Speciálně pokud každá klauzule má právě tři literály, jde o 3-konjunktivní normální formu. Problém 3SAT je SAT omezený na formule v 3-konjunktivní normální formě.
Věta Problém 3SAT je polynomiálně redukovatelný na problém CLIQUE – zjištění, jestli v grafu je klika dané velikosti.
Důkaz Nechť daná formule ϕ je konjunkce k klauzulí. Vyrobíme k-partitní graf s 3k vrcholy ohodnocenými příslušnými literály, kde propojíme všechny dvojice vrcholů, které jsou mezi různými klauzulemi a nejde o proměnnou a její negaci. Snadno nahlédneme, že tento graf obsahuje k-kliku, právě když formule je splnitelná.
Příklad Méjme formuli
ϕ≔(x∨x∨y)∧(x¯∨y¯∨y¯)∧(x¯∨y∨y).
TBD: obrázek
Věta Cookova–Levinova, 1971 Problém SAT je 𝖭𝖯-úplný.
Důkaz Mějme nějaký jazyk L∈𝖭𝖯 přijímaný nedeterministickým Turingovým strojem 𝒜 v čase 𝒪(nk). Pro daký vstup w∈A* délky n uvažujeme tabulku velikosti nk×nk. V prvním a posledním sloupci bude speciální symbol, který se nikde jinde nevyskytuje. Na i-tém řádku (číslováno od nuly) bude zakódovaný stav automatu po provedení i kroků (kde uvažujeme jednu konkrétní větev výpočtu). Tabulku nazveme akceptující, pokud nějaký její řádek odpovídá přijímající konfiguraci. Nyní podle tohoto schématu sestrojíme booleovskou formuli, která bude splněna, právě když existuje akceptující tabulka. Vytvoříme proměnné xi,j,s reprezentující, jestli v buňce s indexem i,j je symbol s. Formule se bude skládat ze čtyř kusů spojených konjunkcí Φ=Φbuňky∧Φstart∧Φúspěch∧Φpřechody:
  1. První část zajistí, aby hodnota každé buňky byla jednoznačně určena:
    Φbuňky≔⋀i,j((⋁sxi,j,s)∧⋀s,t(x¯i,j,s∨x¯i,j,t)).
  2. Druhá část zajistí, že první řádek odpovídá počátečnímu stavu:
    Φstart≔x1,1,#∧x1,2,w1∧x1,3,w2∧⋯∧x1,nk−1,𝙱∧x1,nk,#.
  3. Třetí část zajistí, že automat se dostane do přijímajícího stavu:
    Φúspěch≔⋁i,jxi,j,qF.
  4. Čtvrtá část zajistí, že každá dvojice sousedních řádků odpovídá přechodu 𝒜. Její tvar sem nebudu explicitně vypisovat, protože je pochopitelně pěkně nechutný. Princip je takový, že okno (podtabulku) velikosti 2×3 nazveme legální, pokud neodporuje tvaru přechodové funkce. Do formule potom dáme konjunkci přes všechna okna, že jsou legální.
Důsledek Dá-li se SAT polynomiálně redukovat na nějaký problém, potom tento problém je 𝖭𝖯-těžký.
Věta Problém 3SAT je 𝖭𝖯-úplný.
Důkaz Nejprve dokážeme, že SAT v konjunktivní normální formě se dá převést na 3SAT. Převedeme každou klauzuli v závislosti na dělce podle následujícího algoritmu (kde zi jsou čerstvé proměnné pro každou klauzuli):
(x1)↦(x1∨x1∨x1),
(x1∨x2)↦(x1∨x2∨x2),
(x1∨x2∨x3)↦(x1∨x2∨x3),
(x1∨x2∨x3∨x4)↦(x1∨x2∨z1)∧(z¯1∨x3∨x4),
(x1∨x2∨x3∨x4∨x5)↦(x1∨x2∨z1)∧(z¯1∨x3∨z2)∧(z¯2∨x4∨x5),
a tak dále. Zbývá tedy vyřešit, jak převést každou formuli do konjunktivní normální formy. Mohli bychom zkusit prostě všechno vyjádřit pomocí konjunkce a disjunkce a postupně aplikovat distributivní zákon. Problém je v tom, že by tím mohlo dojít k exponenciálnímu nárůstu. Například formule
⋁j=1n(x1,j∧x2,j)
by se tím změnila na
⋀i1,…,in=12⋁j=1nxij,j.
Existuje algoritmus, který to umí převést s nejvýše polynomiálním nárůstem, ale ten si ukazovat nebudeme. Místo toho stačí do konjunktivní normální formy převést formule z důkazu předchozí věty. Vidíme, že Φbuňky,Φstart,Φúspěch už v ní jsou. Φpřechody je konjunkce přes všechna okna, takže stačí kontrolu každého okna dostat do konjunktivní normální formy. Ta vypadá nějak následovně:
⋁(a1,…,a6)∈legální okna(xi,j,a1∧xi,j+1,a2∧xi,j+1,a3∧xi+1,j,a4∧xi+1,j+1,a5∧xi+1,j2,a6).
Sice není v konjunktivní normální formě, ale snadno ji tam pomocí distributivity můžeme převést. Velikost sice bude exponenciální v počtu oken, ale to je konstanta nezávislá na vstupu.
Důsledek Dá-li se 3SAT polynomiálně redukovat na nějaký problém, potom tento problém je 𝖭𝖯-těžký.
Příklad Mějme problém VERTEXCOVER, kde máme zjistit, jestli daný graf obsahuje vrcholové pokrytí dané velikosti. Dokážeme, že tento problém je 𝖭𝖯-úplný. Snadno vidíme, že je 𝖭𝖯, takže zbývá ukázat, že se na něj dá převést 3SAT. Vezměme nějakou 3CNF formuli. Pro každou proměnnou x vytvoříme udělátko proměnných: dva vrcholy x,x¯ propojené hranou. Pro každou klauzuli l1∨l2∨l3 vytvoříme udělátko klauzule: trojúhelník l1,l2,l3 a každý vrchol v něm spojíme s odpovídajícím vrcholem v udělátku proměnné. Následně se zeptáme, jestli tento graf má pokrytí velikosti m+2n, kde m je počet vrcholů a n je počet klauzulí. Dokážeme, že formule je splnitelná, právě když takové pokrytí existuje.
(⇒)
Vytvoříme pokrytí, kde v každém udělátku proměnné vybereme vrchol odpovídající její hodnotě a v každém udělátku klauzule vybereme dva nesplněné vrcholy (ty jsou nanejvýš dva).
(⇐)
Každé pokrytí musí nutně obsahovat jeden vrchol z každého udělátka proměnné a dva vrcholy z každého udělátka klauzule. Poté stačí přiřadit proměnné podle toho, které vrcholy v udělátcích proměnných byly vybrány.
Příklad Dokážeme 𝖭𝖯-úplnost problému zjištění, zda v orientovaném grafu existuje hamiltonovská cesta (HAMPATH). Příslušnost to 𝖭𝖯 opět ověříme snadno, takže jdeme převádět 3SAT. Tentokrát udělátko každé klauzule bude jen jeden vrchol. TBD: na tohle je potřeba obrázek, aby to dávalo smysl
Příklad Dokážeme 𝖭𝖯-úplnost problému zjištění, zda v neorientovaném grafu existuje hamiltonovská cesta (UHAMPATH). Tentokrát to uděláme tak, že na to převedeme HAMPATH. Vezměme orientovaný graf G, kde chceme najít hamiltonovskou cestu z s do t. Za každý vrchol u∈V(G) vytvoříme tři vrcholy uin,umid,uout, až na to, že s bude mít jen sout a t bude mít jen tin. Přitom uin,umid a umid,uout budou spojené hranou. Dále pro každou hranu (u,v)∈E(G) propojíme {uout,vin}. Snadno dokážeme, že v původním grafu existuje hamiltonovská cesta z s do t, právě když v novém grafu existuje hamiltonovská cesta z sout do tin.
Definice Prostorová složitost Turingova stroje je funkce f:ℕ→ℕ, která číšlu n přiřadí maximální počet polí pásky, jež může stroj navštívit během výpočtu se vstupem délky n. (U nedeterministického stroje bereme maximum přes všechny možné větve výpočtu.)
Definice Pro danou funkci f:ℕ→ℝ+ značíme
Příklad Problém SAT je ve 𝖲𝖯𝖠𝖢𝖤(n), protože při zkoušení hrubou silou použijeme jen lineární množství paměti.
Věta Označme ALLNKA množinu slov kódujících všechny nedeterministické konečné automaty, které přijímají všechna slova. Potom ALLNKA¯∈𝖭𝖲𝖯𝖠𝖢𝖤(n).
Důkaz Na vstupu dostaneme automat. Umístíme žetony na počáteční stavy. Následně nedeterministicky tipneme slovo a budeme podle něj posouvat žetony. Pokud tím odhalíme, že by automat slovo odmítl, vrátíme kladnou odpověď. Přitom stačí provést 2d kroků, kde d je počet stavů, protože jinak se musí nějaká konfigurace zopakovat.
Věta Savitch Nechť f:ℕ→ℝ+ je funkce taková, že f(n)≥n. Potom
𝖭𝖲𝖯𝖠𝖢𝖤(f(n))⊂𝖲𝖯𝖠𝖢𝖤(f2(n)).
Důkaz Vyřešíme obecnější problém. Máme daný nedeterministický automat a chceme zjistit, jestli se může dostat z konfigurace c1 do konigurace c2 v čase t s použitím prostoru f(n). To budeme dělat rekurzivně. Pokud t=1, je to jednoduché. Pokud t>1, pro všechny možné konfigurace c se podíváme, jestli se jde dostat z c1 do c v t2 krocích a z c do c2 v t2 krocích. Pro jednoduchost si nedeterministický automat upravíme, aby přijímal jen jednou možnou konfigurací: přidáme mazací stav, ve kterém smaže celou pásku a až poté přejde do koncového. Označíme d konstantu takovou, že N má maximálně 2d⋅f(n) konfigurací. Poté zbývá rekurzivně zjistit, jestli se z počáteční konfigurace dostaneme do koncové konfigurace v 2d⋅f(n) krocích.
Definice Třídu všech problémů rozhodnutelných deterministickým Turingovým strojem v polynomiálním prostoru značíme 𝖯𝖲𝖯𝖠𝖢𝖤.
𝖯𝖲𝖯𝖠𝖢𝖤≔⋃k𝖲𝖯𝖠𝖢𝖤(nk).
Analogicky
𝖭𝖯𝖲𝖯𝖠𝖢𝖤≔⋃k𝖭𝖲𝖯𝖠𝖢𝖤(nk).
Poznámka Díky předchozí větě je 𝖯𝖲𝖯𝖠𝖢𝖤=𝖭𝖯𝖲𝖯𝖠𝖢𝖤.

Když máme danou prostorovou složitost f(n) stroje, co můžeme říct o jeho časové složitosti? Možných konfigurací (včetně polohy hlavy) je f(n)⋅𝒪(2f(n)), takže pokud se stroj nezacyklí, jeho časová složitost bude nejvýše tohle. Z toho máme

𝖯⊂𝖭𝖯⊂𝖯𝖲𝖯𝖠𝖢𝖤=𝖭𝖯𝖲𝖯𝖠𝖢𝖤⊂𝖤𝖷𝖯𝖳𝖨𝖬𝖤.

U žádné z nerovností nevíme, jestli jde o rovnost. Akorát si později ukážeme, že 𝖯≠𝖤𝖷𝖯𝖳𝖨𝖬𝖤, takže alespoň jedna nerovnost je vlastní. Většina odborníků se domnívá, že všechny nerovnosti jsou vlastní.

Definice Jazyk je 𝖯𝖲𝖯𝖠𝖢𝖤-úplný, pokud je v 𝖯𝖲𝖯𝖠𝖢𝖤 a každý problém z 𝖯𝖲𝖯𝖠𝖢𝖤 je na něj převoditelný.
Příklad Mějme problém TQBF (Totally Qualified Boolean Formula). Uvažujeme booleovské formule, které mohou navíc obsahovat existenční a všeobecný kvantifikátor, přičemž každá proměnná musí být kvantifikovaná. Například formule
ϕ≔∀x∃y((x∨y)∧(x¯∨y¯))
je pravdivá, ale formule
ϕ≔∃x∀y((x∨y)∧(x¯∨y¯))
není pravdivá. Cílem je určit, jestli daná formule je pravdivá.
Věta Meyerova–Stockmeyerova Problém TQBF je 𝖯𝖲𝖯𝖠𝖢𝖤-úplný.
Poznámka Pokud bychom se to pokusili dokázat stejným způsobem jako Cookovu–Levinovu větu, narazili bychom na problém, že tabulka by mohle mít nadpolynomiální výšku, takže by vzniklá formule nebyla polynomiálně velká.
Důkaz Nejdřív dokážeme, že problém je v 𝖯𝖲𝖯𝖠𝖢𝖤, a to konstrukcí rekurzivního algoritmu. Dostaneme na vstupu nějakou formuli φ. Pokud φ nemá žádné proměnné, prostě ji vyhodnotíme. Pokud φ=∃x(ψ), zavoláme algoritmus rekurzivně s tím, že v ψ nahradíme x postupně nulou a jedničkou a podíváme se, jestli to pro alespoň jednu hodnotu vyjde. Analogicky pro φ=∀x(ψ). Jelikož formule je plně kvantifikovaná, tím jsme vyčerpali všechny možnosti. Hloubka rekurze je jistě omezená počtem proměnných.

Nyní mějme libovolný deterministický Turingův stroj a chceme ho v polynomiálním prostoru redukovat na TQBF, tedy pro daný vstup vyprodukovat plně kvantifikovanou booleovskou formuli, která je pravdivá, právě když náš stroj přijímá náš vstup. Pro jednoduchost si automat upravíme, aby měl jedinou přijímacící konfiguraci. Nechť d je konstanta taková, že 𝒜 má při výpočtu se vstupem délky n maximálně 2d⋅f(n) konfigurací. Pro dané t budeme řešit úlohu, jestli se 𝒜 dokáže dostat z konfigurace α do konfigurace β v maximálně t krocích. Pro t=0 nebo t=1 to uděláme analogicky jako v Cookově–Levinově důkazu. Pro vyšší t bychom mohli zkusit použít formuli

∃γ(φα,γ,t2∧φγ,β,t2).
To by ale vedlo k tomu, že délka formule by mohla být lineární v t, což nechceme. Místo toho použijeme formuli
φα,β,t≔∃γ∀(μ,ν)∈{(α,γ),(γ,β)}(φμ,ν,t2).
Zápisem ∃γ ve skutečnosti myslíme, že konfigurace je nějak zakódovaná do logických proměnných jako v Cookově–Levinově důkazu.
Příklad Formulová hra je logická formule ve tvaru
φ=∃x1∀x2∃x3∀x4⋯(ψ),
kde ψ neobsahuje žádné kvantifikátory. První hráč (Eva) vybírá hodnoty kvantifikátorů ∃ a vyhraje, pokud výsledná formule bude pravdivá. Druhý hráč (Adam) vybírá hodnoty ∀ a vyhraje, pokud výsledná formule je nepravdivá. Zjevně pravdivost původní kvantifikované formule odpovídá tomu, který hráč má výherní strategii. Snadno ukážeme, že problém zjištění, který hráč má výherní strategii, je 𝖯𝖲𝖯𝖠𝖢𝖤-úplný.
Příklad Mějme hru, kde je daný graf G s počátečním vrcholem s. Hráč táhne po hraně do ještě nenavštíveného vrcholu. Kdo nemůže táhnout, prohrál. Dokážeme, že tato hra je 𝖯𝖲𝖯𝖠𝖢𝖤-úplná. Nejprve zkonstruujeme rekurzivní algoritmus, abychom dokázali, že je v 𝖯𝖲𝖯𝖠𝖢𝖤. Pokud dG−(s)=0, vstup zamítneme. Jinak pro všechny vrcholy v z NG−(s) rekurzivně zavoláme algoritmus s (G−s,v).

Nyní chceme převést formulovou hru na tuto hru, abychom dokázali 𝖯𝖲𝖯𝖠𝖢𝖤-úplnost. Část formule za kvantifikátory si převedeme do konjunktivní normální formy. Udělátko každé proměnné bude diamant (TBD: obrázek).

Poznámka Je-li B 𝖯𝖲𝖯𝖠𝖢𝖤-úplný problém a B∈𝖯, potom 𝖯=𝖯𝖲𝖯𝖠𝖢𝖤.
Definice Mějme dvoupáskový Turingův stroj, kde na první pásce je vstup, smí se z ní pouze číst a hlava nesmí opustit prostor vymezený vstupem. Druhá páska je pracovní a začíná prázdná. Třída 𝖫 je třída jazyků rozhodnutelných na tomto stroji s logaritmickou prostorovou složitostí, přičemž počítáme jen pracovní pásku (jinak by složitost nemohla být lepší než lineární). Nedeterministická verze je třída 𝖭𝖫.
Příklad Jazyk {𝖺n𝖻n|n∈ℕ} je třídy 𝖫, protože můžeme prostě spočítat písmena.
Příklad Ukážeme, že problém PATH je třídy 𝖭𝖫. (Nikdo neví, jestli je třídy 𝖫). Vyrazíme z počátečního vrcholu a vždy si nedeterministicky vybereme, kam jít. Zároveň si budeme počítat, kolik kroků jsme udělali, a skončíme, pokud jich bude stejně jako počet vrcholů.
Věta Nechť stroj s vstupní a pracovní páskou pracuje s prostorovou složitostí f(n). Potom jeho časová složitost je n⋅2𝒪(f(n)). Speciálně pokud f(n)≥logn, potom časová složitost je 2𝒪(f(n)).
Důkaz Konfigurace stroje je jednoznačně určena stavem, obsahem pracovní pásky a pozicí dvou hlav.
Důsledek 𝖫⊂𝖯.
Poznámka Modifikací lze dokázat, že to platí i pro klasický jednopáskový Turingův stroj.
Definice Log-space převodník je Turingův stroj s vstupní, pracovní a výstupní páskou, kde:Log-space převodník vyčísluje funkci f:Σ*→Σ*, pokud po spuštění se vstupem w zůstane na výstupní pásce f(w). Jazyk A je log-space převoditelný na jazyk B, pokud existuje log-space vyčíslitelná funkce f taková, že ∀w∈Σ*:w∈A⟺f(w)∈B. Značíme A≤LB.
Definice Jazyk A je
Věta Je-li A≤LB a B∈𝖫, potom A∈𝖫.
Důkaz Důkaz není tak přímočarý jako u 𝖯, protože převodní algoritmus může vyprodukovat výstup s větší než logaritmickou velikostí. Místo toho budeme f(w) počítat „líně“: spustíme algoritmus pro řešení B s virtuální páskou, která pokaždé, když se z ní má něco přečíst, spustí převodní algoritmus a zastaví ho v okamžiku, kdy dostane znak na správné pozici.
Důsledek Je-li nějaký problém 𝖭𝖫-úplný a zároveň v 𝖭𝖫, potom 𝖫=𝖭𝖫.
Věta Problém PATH je 𝖭𝖫-úplný.
Důkaz Stačí dokázat, že je 𝖭𝖫-těžký. Mějme nějaký log-space nedeterministický stroj pro nějaký problém, který bez újmy na obecnosti má jedinou přijímající konfiguraci. Sestrojíme graf, jehož vrcholy budou konfigurace stroje a hrany budou možné přechody. Tím jsme problém převedli na hledání cesty z počáteční do koncové konfigurace. Snadno dokážeme, že převod je log-space.
Důsledek 𝖭𝖫⊂𝖯.
Důkaz Log-space převodník pracuje v polynomiálním čase, takže jakýkoli problém z 𝖭𝖫 dokážeme polynomiálně převést na problém PATH, který je v 𝖯.

Již máme posloupnost nerovností:

𝖫⊂𝖭𝖫⊂𝖯⊂𝖭𝖯⊂𝖯𝖲𝖯𝖠𝖢𝖤=𝖭𝖯𝖲𝖯𝖠𝖢𝖤⊂𝖤𝖷𝖯𝖳𝖨𝖬𝖤.
Definice Nedeterministický Turingův stroj počítá funkci f:Σ*→Σ*, pokud pro každý vstup w∈Σ* platí, že každá větev výpočtu buď přijme w a na pásce zbyde f(w), nebo vstup zamítne, přičemž alespoň jedna větev ho přijme.
Věta PATH¯∈𝖭𝖫.
Důkaz Mějme funkci path(G,s,t), která vrací 1, pokud v G existuje cesta z s do t, a 0 jinak. Zkonstruujeme nedeterministický Turingův stroj, který počítá tuto funkci. Definujme dvě další funkce: R(G,s) je množina vrcholů, do kterých se dá dostat z s, a c(G,s)≔#R(G,s).
Lemma Existuje-li log-space nedeterministický Turingův stroj počítající funkci path, potom také existuje stroj počítající funkci c.
Důkaz Postupně projdeme všechna možná t a spočítáme je.
Lemma Existuje-li log-space nedeterministický Turingův stroj počítající funkci c, potom také existuje stroj počítající funkci path.
Důkaz Spočteme si, kolik existuje dosažitelných vrcholů. Poté si nedeterministicky tipneme, které to jsou, a nedeterministicky otestujeme, jestli jsou skutečně dosažitelné. Pokud zarhnují t, potom vrátíme 1, jinak vrátíme 0. Tipneme-li špatně, vstup zamítneme.
Nyní analogicky definujeme funkce pathd,Rd,cd, které uvažují pouze cesty délky d∈ℕ.
Lemma Existuje-li log-space nedeterministický Turingův stroj počítající funkci pathd, potom také existuje stroj počítající funkci cd.
Důkaz Analogicky.
Lemma Existuje-li log-space nedeterministický Turingův stroj počítající funkci cd, potom také existuje stroj počítající funkci pathd.
Důkaz Analogicky.
Lemma Existuje-li log-space nedeterministický Turingův stroj počítající funkci cd, potom také existuje stroj počítající funkci pathd+1.
Důkaz Podobně, ale místo abychom kontrolovali, jestli jeden z vybraných vrcholů je t, zkontrolujeme, jestli z nějakého vybraného vrcholu vede hrana do t.
Lemma Existuje-li log-space nedeterministický Turingův stroj počítající funkci cd, potom také existuje stroj počítající funkci cd+1.
Nyní již konečně můžeme sestavit kýžený algoritmus. Víme c0(G,s)=1. Pro každé d=1,…,m spočteme cd na základě cd−1. Poté pomocí cm spočteme pathm=path.
Důsledek 𝖭𝖫=𝖼𝗈𝖭𝖫, kde 𝖼𝗈𝖭𝖫 je definována analogicky jako 𝖼𝗈𝖭𝖯.
Definice Funkce f:ℕ→ℝ0+ splňující f(n)=Ω(logn) je prostorově konstruovatelná, pokud funkce, která pro vstup 𝟣n vrátí binární reprezentaci ⌊f(n)⌋, je vyčíslitelná s prostorovou složitostí 𝒪(f(n)).
Věta o prostorové hierarchii Pro libovolnou prostorově konstruovatelnou funkci f:ℕ→ℕ existuje jazyk Af, který je rozhodnutelný s prostorovou složitostí 𝒪(f(n)) a není rozhodnutelný s prostorovou složitostí ℴ(f(n)).
Důkaz Sestrojíme automat 𝒟, který dostane nějaké slovo w. Napřed si na pásce vyznačí f(n) políček. Pokud následně někdy překročí tuto hranici, vstup zamítne. Následně se podívá, jestli w kóduje nějaký Turingův stroj 𝒜. Pokud ne, tak ho zamítne. Pokud ano, podívá se, jestli 𝒜 přijímá w, a odpověď zneguje. Tento přístup má několik problémů:Zřejmě platí, že 𝒟 má prostorovou složitost 𝒪(f(n)). Zároveň z konstrukce plyne, že nemůže rozeznávat stejný jazyk jako nějaký automat s prostorovou složitostí ℴ(f(n)).
Důsledek Jsou-li f1,f2:ℕ→ℕ funkce takové, že f1(n)=ℴ(f2) a f2 je prostorově konstruovatelná, potom 𝖲𝖯𝖠𝖢𝖤(f1(n))⊊𝖲𝖯𝖠𝖢𝖤(f2(n)).
Důsledek 𝖭𝖫⊊𝖯𝖲𝖯𝖠𝖢𝖤.
Důkaz Podle Savitchovy věty je 𝖭𝖫⊂𝖲𝖯𝖠𝖢𝖤(log2n). Podle věty o prostorové hierarchii je 𝖲𝖯𝖠𝖢𝖤(log2n)⊊𝖯𝖲𝖯𝖠𝖢𝖤.
Důsledek 𝖯𝖲𝖯𝖠𝖢𝖤⊊𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤.
Definice Funkce f:ℕ→ℝ0+ splňující f(n)=Ω(logn) je časově konstruovatelná, pokud funkce, která pro vstup 𝟣n vrátí binární reprezentaci ⌊f(n)⌋, je vyčíslitelná s časovou složitostí 𝒪(f(n)).
Věta o časové hierarchii Pro libovolnou prostorově konstruovatelnou funkci f:ℕ→ℕ existuje jazyk Af, který je rozhodnutelný s časovou složitostí 𝒪(f(n)) a není rozhodnutelný s časovou složitostí ℴ(f(n))logf(n).
Důkaz Opět sestrojíme automat 𝒟, který dostane nějaké slovo w. Napřed si spočte hodnotu ⌈f(n)⌉logn a uloží ji do čítače. Následně se podívá, jestli w kóduje ⟨M⟩10* pro nějaký Turingův stroj M. Pokud ne, tak ho zamítne. Pokud ano, odsimuluje stroj M s omezeným počtem kroků podle čítače. Pokud M skončí a zamítne vstup, potom ho 𝒟 přijme, jinak ho odmítne.

Nyní již nebude úplně triviální dokázat, že simulaci dokážeme provést v čase 𝒪(f(n)). Budeme si muset všechny potřebné informace „držet blízko sebe“. Simulace bude probíhat tak, že

Problém je, že ve skutečnosti máme jen jednu hlavu, takže její pohyb mezi páskami by mohl zabrat hodně času. To vyřešíme tak, že při každém pohybu hlavy na první pásce posunume celý obsah druhé a třetí pásky k ní. To nás může stát 𝒪(logf(n)) času, proto je ve znění věty nutné dělit logf(n).

Podívejme se opět na naši posloupnost nerovností:

𝖫⊂𝖭𝖫⊂𝖯⊂𝖭𝖯⊂𝖯𝖲𝖯𝖠𝖢𝖤=𝖭𝖯𝖲𝖯𝖠𝖢𝖤⊂𝖤𝖷𝖯𝖳𝖨𝖬𝖤⊂𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤,

přičemž víme 𝖭𝖫≠𝖯𝖲𝖯𝖠𝖢𝖤, 𝖯≠𝖤𝖷𝖯𝖳𝖨𝖬𝖤 a 𝖯𝖲𝖯𝖠𝖢𝖤≠𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤, ale jinak toho nevíme moc.

Definice Problém A je 𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤-úplný, pokud A∈𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤 a pro každý B∈𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤 je B≤PA. Analogicky definujeme 𝖤𝖷𝖯𝖳𝖨𝖬𝖤-úplnost.
Definice Regulární výrazy E,F jsou ekvivalentní, pokud [E]=[F]. Značíme E≡F. Dále označíme problém
EQREX≔{⟨E,F⟩|E≡F}.
Věta EQREX∈𝖯𝖲𝖯𝖠𝖢𝖤.
Důkaz Dokážeme, že EQREX∈𝖼𝗈𝖭𝖯𝖲𝖯𝖠𝖢𝖤. Z toho to už plyne, protože podle nějaké věty je 𝖼𝗈𝖭𝖯𝖲𝖯𝖠𝖢𝖤=𝖼𝗈𝖯𝖲𝖯𝖠𝖢𝖤=𝖯𝖲𝖯𝖠𝖢𝖤.

Dané dva regulární výrazy převedeme na nedeterministické konečné automaty. Poté si nedeterministicky tipneme slovo w a posouváním žetonků budeme simulovat všechny možné výpočty s tímto slovem. Pokud se pro nějaké slovo dostaneme do stavu, kde v jednom automatu budou všechny žetonky v nekoncových stavech a ve druhém bude nějaký v koncovém stavu, potom w∈[E]▵[F]. Pokud takové slovo nenajdeme, potom [E]=[F].

Tím jsme zatím nedostali příklad 𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤-úplného problému. Co když ale v regulárních výrazech povolíme mocniny?

Definice Regulární výraz s mocninou je regulární výraz, kde navíc povolujeme operaci Rk≔R⋯R⏟k× pro k∈ℕ. Pro regulární výrazy s mocninami označíme problém
EQREX↑≔{⟨E,F⟩|E≡F}.
Věta Problém EQREX↑ je 𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤-úplný.
Důkaz Snadno dokážeme, že EQREX↑∈𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤: stačí natvrdo rozepsat mocniny z definice (což způsobí exponenciální nárůst) a použít algoritmus z předchozí věty. Nyní se na to pokusíme převést libovolný problém z 𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤. Nechť problém A je rozhodnutelný deterministickým Turingovým strojem M v čase 𝒪(2nk). Stroj M používá nějakou abecedu Δ≔Q∪Γ∪{#}. Myšlenka algoritmu bude taková, že pro dané slovo w sestrojíme regulární výraz představující všechno kromě posloupnosti konfigurací, pomocí kterých M přijímá w. Poté se stačí podívat, jestli je tento regulární výraz ekvivalentní Δ*. Výraz se bude skládat z částí:
R≔Rzačátek∪Rvýpočet∪Rkonec.
Pro jednoduchost si pro dané b∈Δ označme
Δε≔Δ∪{ϵ},Δ−b≔Δ∖{b}.
Budeme mít
Si≔ΔnΔ−wnΔ*
Rzačátek≔⋃iSi,
Rkonec≔Δ−qreject*,
Rvýpočet≔⋃[abcdef]nelegální oknoΔ*abcΔ2nk−3defΔ*.
Definice Turingův stroj s orákulem pro problém A je hypotetický Turingův stroj, který navíc dokáže magicky vyřešit libovolnou instanci problému A v konstantním čase. Pro takové stroje můžeme označit třídy problémů 𝖯A, 𝖭𝖯A, apod.
Věta Existuje orákulum A takové, že 𝖯A=𝖭𝖯A, a orákulum B takové, že 𝖯B≠𝖭𝖯B.
Důkaz Nestihli jsme ☹ Konkrétně se jako jedno z orákulí dá použít TQBF, protože
𝖭𝖯TQBF⊂𝖭𝖯𝖲𝖯𝖠𝖢𝖤⊂𝖯𝖲𝖯𝖠𝖢𝖤⊂𝖯TQBF.
Důsledek Není možné dokázat jen pomocí diagonalizace, že 𝖯=𝖭𝖯 nebo 𝖯≠𝖭𝖯 (protože potom by stačilo do takového důkazu přidat orákulum a měli bychom spor).