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 TIME(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 TIME(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:
𝐏=⋃kTIME(nk).
Poznámka U třídy 𝐏 na rozdíl od tříd TIME(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 NTIME(t(n)) je třída všech jazyků, které jsou rozhodnutelné na nedeterministickém Turingově stroji v čase 𝒪(t(n)).
Poznámka
𝐍𝐏=⋃k∈ℕNTIME(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
EXPTIME≔⋃k∈ℕTIME(2nk).
Poznámka Platí 𝐍𝐏⊂EXPTIME.
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 Cook-Levin, 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 SPACE(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¯∈NSPACE(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
NSPACE(f(n))⊂SPACE(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 PSPACE.
PSPACE≔⋃kSPACE(nk).
Analogicky
NPSPACE≔⋃kNSPACE(nk).
Poznámka Díky předchozí větě je PSPACE=NPSPACE.

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

𝐏⊂𝐍𝐏⊂PSPACE⊂EXPTIME.

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

Definice Jazyk je NPSPACE-úplný, pokud je v NPSPACE a každý problém z NPSPACE 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á.