Jméno: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. (a) Která z následujících tvrzení jsou pravdivá? Svou odpověď zdůvodněte. (i) Množina A1 ⊆ N je rekurzivní právě tehdy, když existuje totálně vyčislitelná funkce f taková, že x ∈ A1 ⇔ ∀x′ < x : f(x) > f(x′). (ii) Množina A2 ⊆ N obsahující ty i ∈ N, že se i-tý while-program zastaví pro nějaký vstup, je rekurzivní. (iii) Množina A2 ⊆ N z předchozího bodu je rekurzivně spočetná. (b) Definujte, co znamená, že rozhodovací problém je polynomiálně redukovatelný na jiný rozhodovací problém. Platí, že každý NP-úplný problém je polynomiálně redukovatelný na každý PSPACE-úplný problém? Svou odpověď zdůvodněte. (a) (i) Není pravdivé. Množina A1 = {1} je rekurzivní, ale libovolná funkce f splňuje ∀x′ < 0 : f(0) > f(x′). Na dalším listu je uvedeno nesprávné řešení této části příkladu, za které bychom také dali plný počet bodů - nebylo naším úmyslem vytvořit „chyták . (ii) Není pravdivé. Množina A2 je netriviální množina, která respektuje funkce, a není tedy rekurzivní dle První Riceovy věty. (iii) Je pravdivé. Následující algoritmus se zastaví právě tehdy, když i ∈ A2. Postupně pro k = 1, 2, . . . budeme simulovat prvních k kroků výpočtu i-tého programu na vstupech 1, . . . , k. Pokud pro nějaké k a nějaký vstup simulace skončí, pak se popisovaný algoritmus zastaví. Pokud takové k nikdy nenalezneme, pak se popisovaný algoritmus nikdy nezastaví. To ale nastane jen tehdy, pokud se i-tý program pro žádný vstup nezastaví. Existence výše popsaného algoritmu dokazuje, že A2 je rekurzivně spočetná. (b) Problém P je polynomiálně redukovatelný na problém Q, pokud existuje polynomiální algoritmus A, t.ž. x ∈ P právě tehdy, když A(x) ∈ Q pro všechny možné vstupy x, kde A(x) je výstup algoritmu A pro x. Ano, platí. Nechť P je PSPACE-úplný problém. Protože každý problém ze třídy PSPACE je na P polynomiálně redukovatelný, každý NPúplný problém patří do NP dle definice NP-úplnosti a NP ⊆ PSPACE, je každý NP-úplný problém polynomiálně redukovatelný na P. Oblast strojově snímatelných informací, nezasahujte. Jméno: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. (a) Která z následujících tvrzení jsou pravdivá? Svou odpověď zdůvodněte. (i) Množina A1 ⊆ N je rekurzivní právě tehdy, když existuje totálně vyčislitelná funkce f taková, že x ∈ A1 ⇔ ∀x′ < x : f(x) > f(x′). (ii) Množina A2 ⊆ N obsahující ty i ∈ N, že se i-tý while-program zastaví pro nějaký vstup, je rekurzivní. (iii) Množina A2 ⊆ N z předchozího bodu je rekurzivně spočetná. (b) Definujte, co znamená, že rozhodovací problém je polynomiálně redukovatelný na jiný rozhodovací problém. Platí, že každý NP-úplný problém je polynomiálně redukovatelný na každý PSPACE-úplný problém? Svou odpověď zdůvodněte. (a) (i) Toto řešení je chybné – viz komentář na předchozím listu. Je pravdivé. Ekvivalenci dokazujeme jako dvě implikace. A1 je rekurzivní ⇒ existence funkce f ze zadání. Nechť f(x) je počet hodnot y ≤ x, t.ž. y ∈ A1. Funkci f je součtem prvních x hodnot charakteristické funkce množiny A1 a je tedy totálně vyčislitelná. Pokud x ∈ A1, pak f(x) = f(x − 1) a tedy neplatí ∀x′ < x : f(x) > f(x′). Pokud x ∈ A1, pak f(x) > f(x′) pro všechna x′ < x. (Tento argument selhává pro x = 0, pokud 0 ∈ A1.) Existence funkce f ze zadání ⇒ A1 je rekurzivní. Následující algoritmus počítá charakteristickou funkci množiny A1. Postupně pro x′ = 0, . . . , x−1 vypočteme f(x′) a ověříme, že f(x′) < f(x). Pokud test někdy selže, pak vystoupíme 0. Jinak vystoupíme 1. (ii) Není pravdivé. Množina A2 je netriviální množina, která respektuje funkce, a není tedy rekurzivní dle První Riceovy věty. (iii) Je pravdivé. Následující algoritmus se zastaví právě tehdy, když i ∈ A2. Postupně pro k = 1, 2, . . . budeme simulovat prvních k kroků výpočtu i-tého programu na vstupech 1, . . . , k. Pokud pro nějaké k a nějaký vstup simulace skončí, pak se popisovaný algoritmus zastaví. Pokud takové k nikdy nenalezneme, pak se popisovaný algoritmus nikdy nezastaví. To ale nastane jen tehdy, pokud se i-tý program pro žádný vstup nezastaví. Existence výše popsaného algoritmu dokazuje, že A2 je rekurzivně spočetná. (b) Problém P je polynomiálně redukovatelný na problém Q, pokud existuje polynomiální algoritmus A, t.ž. x ∈ P právě tehdy, když A(x) ∈ Q pro všechny možné vstupy x, kde A(x) je výstup algoritmu A pro x. Ano, platí. Nechť P je PSPACE-úplný problém. Protože každý problém ze třídy PSPACE je na P polynomiálně redukovatelný, každý NPúplný problém patří do NP dle definice NP-úplnosti a NP ⊆ PSPACE, je každý NP-úplný problém polynomiálně redukovatelný na P. Oblast strojově snímatelných informací, nezasahujte. Jméno: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. (a) Vysvětlete, co znamená, že množina B ⊆ N respektuje funkce. (b) Nechť f : N → N ∪ {⊥} je funkce, t.ž. f(x) = ⊥ pro konečně mnoho x ∈ N, a nechť C je množina těch i ∈ N, že funkce ϕi je rozšířením f. (i) Pro které funkce f je množina C rekurzivní? (ii) Pro které funkce f je množina C rekurzivně spočetná? (iii) Pro které funkce f je množina C rekurzivně spočetná? Své odpovědi zdůvodněte. (a) Množina B respektuje funkce, pokud pro každé dva indexy i a j, t.ž. ϕi = ϕj, platí, že buď jsou oba v B nebo není ani jeden v B. (b) Protože f(x) je různá od ⊥ pouze pro konečně mnoho hodnot x ∈ N, je funkce f vyčíslitelná a tedy existuje α, t.ž. f = ϕα. Dále zvolme β, t.ž. funkce ϕβ cyklí na všech vstupech. (i) Právě tehdy, když f = ϕβ. Pokud f = ϕβ, pak C = N a C je tedy rekurzivní. Pokud f = ϕβ, pak α ∈ C a β ∈ C, a C není rekurzivní dle První Riceovy věty, neboť respektuje funkce a není triviální. (ii) Vždy. Nechť x1, . . . , xk jsou právě ty hodnoty, pro které f(x) = ⊥. Následující algoritmus se zastaví na vstupu i právě tehdy, když i ∈ C: postupně pro j = 1, . . . , k simulujeme i-tý program pro vstup xj a pokud simulace skončí a výsledek není f(xj), tak se algoritmus zacyklí. Pokud simulace skončí pro všech k hodnot x1, . . . , xk a výsledek je vždy f(xj), pak se algoritmus zastaví. Právě popsaný algoritmus se na vstupu i zastaví právě tehdy, když i ∈ C. Platí tedy, že množina C je vždy rekurzivně spočetná. (iii) Právě tehdy, když f = ϕβ. Protože množina C je rekurzivně spočetná, je množina C rekurzivně spočetná právě tehdy, když C je rekurzivní, což jsme vyřešili v první části této podotázky. Oblast strojově snímatelných informací, nezasahujte. Jméno: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. (a) Definujte prostorovou složitost nedeterministického algoritmu. (b) Zformulujete a dokažte větu z přednášky, která hovoří o inkluzi třídy NSPACE(f(n)) pro f(n) ∈ Ω(log n) ve třídě problémů řešitelných deterministicky v omezeném čase. (a) Prostorová složitost nedeterministického algoritmu je funkce f : N → N, t.ž. f(n) se rovná nejmenšímu číslu K, pro které platí, že každá větev výpočtu algoritmu pro libovolný vstup velikost n pracuje v prostoru nejvýše K. (b) Zadání popisuje větu, která říká, že NSPACE(f) ⊆ TIME 2O(f) . Zvolme problém z NSPACE(f) a nedeterministický algoritmus A, který jej řeší v prostoru O(f). Nyní popíšeme deterministický algoritmus, který zvolený problém řeší v čase 2O(f). Pro daný vstup velikosti n a vhodně zvolené číslo s sestavíme pomocný orientovaný graf, jehož vrcholy jsou možné stavy výpočtu algoritmu A, který používá prostor nějvýše s. Takových stavů je nejvýše 2O(s): pokud uvažujeme výpočetní mode Turingových strojů, je stav výpočtu určen stavem stroje, pozicí hlav na vstupní pásce (n možností) a pracovní pásce (s možností) a obsahem pracovní pásky (3s možností v případě binární abecedy). Z vrcholu odpovídajícího stavu s vede hrana do vrcholu odpovídající stavu s′ právě tehdy, když ze stavu s lze přejít v jednom kroku do stavu s′. Pokud je s zvolené tak, že prostorová složitost algoritmu pro danný vtsup je nejvýše s, pak stačí v tomto pomocném grafu ověřit existenci cesty z počátečního stavu výpočtu do některého z přijímajících stavů. To lze snadno udělat v čase v polynomiálním ve velikosti pomocného grafu, tj. v v čase 2O(s). Zbývá tedy popsat, jak nalézt takové číslo s, které zároveň není o mnoho větší než f(n). Nejdříve zvolíme s = 1 a sestavíme pomocný graf pro tuto hodnotu s. Pokud v něm existuje cesta z počátečního stavu výpočtu do stavu, ze kterého lze přejít do stavu používajícího prostor s + 1 (toto lze vyhodnotit v čase 2O(s)), pak zjevně s < f(n) a v takovém případě hodnotu s zdvojnásobíme a postup opakujeme. Zastavíme se nejpozději, když s ≥ f(n). Postup popsaný v prvním odstavci pak použijeme pro tuto hodnotu s. Vzhledem k popsanému postupu bude tedy nakonci platit, že s ≤ 2f(n) a tedy s ∈ O(f). Celková časová složitost právě popsaného algoritmu je tedy 2O(s). Oblast strojově snímatelných informací, nezasahujte.