# Kučera 23.1.2017

<{ForumPost(poster="CiTrus", timestamp=2017-01-24 14:16:59)}>
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).

<{/ForumPost}>