Kučera 23.1.2017

Zkouška vypadala podobně jako minule.

Písemka:

1. Definujeme problém zastavení na prvočíslech.
   Instance: Turingův stroj $M$ zadaný kódem
   Otázka: Existuje prvočíslo $p$ takové, že $M(p)\downarrow$
   Rozhodněte, zda tento problém a jeho doplněk jsou (částečně) rozhodnutelné. Svojí odpověď zdůvodněte.

2. Definujeme problém omezené paměti.
   Instance: Turingův stroj $M$ zadaný kódem, slovo $x\in\Sigma^\ast$ a algoritmicky vyčíslitelná funkce $f:\Sigma^\ast\rightarrow\mathbb{N}$
   Otázka: Vystačí si $M$ při výpočtu nad vstupem $x$ s pamětí $f(x)$?
   Ukažte, že tento problém je rozhodnutelný.

3. Definujeme problém čtyřlisté kostry.
   Instance: Graf $G=(V,E)$
   Otázka: Existuje kostra grafu $G$, která má právě 4 listy?
   Ukažte, že problém je NP-úplný. Můžete použít převod z některého z problémů probíraných na přednášce.

Na písemku byla hodina, při odevzdání se přidělovaly sloty na ústní část po půlhodinách. Po příchodu se losovaly otázky ze seznamu, který je volně k dispozici na webu předmětu. Já jsem dostal NP-úplnost kachlíkování.

Hinty:

1. Problém je částečně rozhodnutelný, ale nikoliv rozhodnutelný. Důkaz vyplývá z Riceovy věty.

2. Je třeba použít lemma o inkluzi $NSPACE(f(n))\subseteq TIME(2^{c_Lf(n)})$, pak pustit $M(x)$ a odmítnout, když překročí vymezenou paměť nebo běží příliš dlouho..

3. Šla na to převést Hamiltonovská cesta (na kterou jde převést Hamiltonovská kružnice).