Čtení: 60 minHodnotí se: ústní zkouška

6 Teorie k ústní zkoušce

Varování 6.1 (Stav materiálů)

Seznam témat ke zkoušce ještě nebyl zveřejněn a v materiálech jsou přednášky jen do 6. Tato kapitola je proto výběr toho nejpodstatnějšího, ne oficiální okruhy. Po zveřejnění ji upravíme.

Po přečtení umíš

vysvětlit vlastními slovy hlavní třídy a vztahy mezi nimi
popsat myšlenku klíčových vět bez detailního důkazu
odpovědět na typické doplňující otázky

U ústní zkoušky se počítá, že umíš věc vysvětlit a uvést příklad. Každou odpověď si proto řekni nahlas dřív, než si ji rozklikneš.

6.1 Mapa tříd

\mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} = \mathrm{NPSPACE} \subseteq \mathrm{EXP}

Třída	Co znamená	Typický problém
L	prostor $O(\log n)$	jednoduché počítání
NL	nedeterministický prostor $O(\log n)$	dosažitelnost v grafu
P	polynomiální čas	souvislost grafu
NP	řešení lze ověřit v polynomiálním čase	SAT, Clique
PSPACE	polynomiální paměť	Geografie, TQBF
EXP	exponenciální čas

Z časové hierarchie víme, že P ≠ EXP. Takže aspoň jedna inkluze mezi P a EXP je ostrá, ale která, nevíme.

6.2 Otázky

Kvíz

1. Proč v teorii složitosti používáme Turingův stroj a rozhodovací problémy?

Ukázat řešení

Dokázat, že něco nejde, vyžaduje formální model všech algoritmů. Rozhodovací problém je jazyk

L \subseteq \Sigma^*

a o optimalizaci nepřijdeme, protože prahové

k

vyhledáme binárně.

2. Co je HaltingProblem a proč je nerozhodnutelný?

Ukázat řešení

Vstupem je stroj

M

a slovo

x

, otázka zní, zda

M

x

skončí. Plyne z nepočitatelnosti funkce UC diagonalizací: kdyby stroj existoval, sestrojíme stroj, který na vlastním popisu udělá opak. Důsledek: nelze napsat univerzální analyzátor kódu.

3. Co říká časová hierarchie?

Ukázat řešení

S asymptoticky více času spočítáme ostře víc: pro časově konstruovatelné funkce, kde

f \log f = o(g)

, platí

\mathrm{DTIME}(f) \subsetneq \mathrm{DTIME}(g)

. Proto P ≠ EXP.

4. Co je třída NP? Uveď obě definice.

Ukázat řešení

Jazyky rozhodované NDTS v polynomiálním čase. Ekvivalentně: jazyky s polynomiálním deterministickým verifikátorem a polynomiálně dlouhým certifikátem. Certifikát odpovídá posloupnosti nedeterministických voleb.

5. Je nedeterminismus paralelismus?

Ukázat řešení

Ne. Je to matematická definice přijetí: stačí jedna přijímající větev. Paralelní stroj má jen konečně mnoho procesorů, zatímco větví může být exponenciálně.

6. Co je redukce a NP-úplnost? Proč jsou užitečné?

Ukázat řešení

A \le_p B

převádí instance v polynomiálním čase a zachovává odpověď. NP-úplný problém je v NP a každý problém z NP se na něj redukuje. Pokud by byl v P, pak P = NP. V praxi přestaneme hledat přesný polynomiální algoritmus.

7. Popiš myšlenku Cook-Levinovy věty.

Ukázat řešení

Pro

L \in

NP se výpočet polynomiálního NDTS zapíše do tabulky čas krát prostor. Formule popisuje správný začátek, každou lokální změnu podle přechodové funkce a přijetí. Přednáška to ukazuje přes dlaždičkování. Formule je polynomiálně velká a splnitelná právě tehdy, když výpočet přijímá.

8. Jaký je rozdíl mezi slabou a silnou NP-těžkostí?

Ukázat řešení

Silně těžký problém zůstává těžký i při unárních číslech. Slabě těžký má pseudopolynomiální algoritmus: Subset Sum v

O(nT)

, Knapsack. Silně těžký je 3-Partition. V praxi: slabě těžký s malými čísly vyřeší dynamické programování.

9. Proč je NP-úplný problém s pseudopolynomiálním algoritmem v souladu s P ≠ NP?

Ukázat řešení

Čas

O(nT)

závisí na hodnotě

T

, ale délka vstupu je jen

\log T

. Vůči délce vstupu je to exponenciální.

10. Co říká Savitchova věta a proč je překvapivá?

Ukázat řešení

\mathrm{NSPACE}(S) \subseteq \mathrm{DSPACE}(S^2)

pro prostorově konstruovatelné

S \ge \log n

. Odstranění nedeterminismu stojí jen kvadraticky, u času neznáme nic takového. Myšlenka: rekurzivně hledáme prostřední konfiguraci výpočtu, hloubka je

O(S)

a každá úroveň potřebuje

O(S)

paměti. Důsledek: PSPACE = NPSPACE.

11. Proč je prostor silnější zdroj než čas, ale čas prostor omezuje?

Ukázat řešení

Za čas

T

se nedá zapsat víc než

T

políček, takže

\mathrm{DTIME}(T) \subseteq \mathrm{DSPACE}(T)

. Naopak prostor lze používat opakovaně a konfigurací je až exponenciálně v prostoru, proto PSPACE ⊆ EXP.

12. Co je PSPACE-úplný problém a příklad?

Ukázat řešení

Je v PSPACE a každý problém z PSPACE se na něj redukuje. Příklady: TQBF a Geografie, hra dvou hráčů. Pro hry je typické střídání tahů, odpovídající střídání kvantifikátorů.

13. Co je

\mathrm{NL}

a proč je dosažitelnost v grafu zajímavá?

Ukázat řešení

NL je nedeterministický logaritmický prostor. Dosažitelnost je v NL: pamatujeme si jen aktuální vrchol a počítadlo kroků. Immerman-Szelepcsényi: NL je uzavřené na doplněk, což se u NP neví.

6.3 Jak odpovídat

Začni definicí jednou větou.
Přidej příklad.
Řekni, proč je to důležité.
Pokud nevíš, popiš, kam až vidíš. Mlčení je nejhorší.

6.4 Tahák

Tahák

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXP, a P ≠ EXP.
NP = hádej a ověř = certifikát.
NP-úplný = v NP a vše z NP se na něj redukuje.
Cook-Levin: výpočet jako tabulka, formule popisuje lokální pravidla.
Slabě těžký: $O(nT)$ existuje. Silně těžký: nepomůžou ani malá čísla.
Savitch: $S \to S^2$ , hledání středu konfigurace.
HaltingProblem: diagonalizace, nerozhodnutelné.

Kapitolu mám prostudovanou