# Kučera 19.1.

<{ForumPost(poster="Aearsis", timestamp=2017-01-19 18:05:06)}>
1. Ukažte, že následující problém není algoritmicky rozhodnutelný:  
Pomalejší TS  
**Instance:** Dva TS M<sub>1</sub> a M<sub>2</sub> zadané svými kódy.  
**Otázka:** Platí pro každé x ∈ Σ*, že M<sub>1</sub> vykoná při práci nad vstupem x alespoň tolik kroků, kolik jich se vstupem x vykoná M<sub>2</sub>?  
Rozhodněte (a zdůvodněte), zda tento problém nebo jeho doplněk je částečně rozhodnutelný.  
  
2. Rozhodněte, zda mezi třídami NSPACE(n *log* n) a TIME(2<sup>n²</sup>) platí nějaký vztah (inkluze, ostrá inkluze), nebo není možné takový vztah ukázat na základě tvrzení, jež jsme probírali na přednášce.  
  
3. S pomocí některého z problémů Kachlíkování, 3-Splnitelnost, Vrcholové pokrytí, 3D párování, Hamiltonovská kružnice, Obchodní cestující nebo Loupežníci ukažte, že následující problém je NP-úplný:  
  
Hitting set  
**Instance:** Množina S a množina C podmnožin množiny S, přirozené číslo k > 0.  
**Otázka:** Existuje $S' \subset S, |S'| \leq k$ taková, že S' obsahuje nejméně jeden prvek z každé množiny v C?  
  

----

Spoiler:  
1. Buď M<sub>1</sub> TS, který se na každém vstupu zacyklí -> Halting problém. Doplněk je částečně rozhodnutelný - NTS uhodne protipříklad.   
2. $NSPACE(n \log n) \subset TIME(2^{n^2})$ - přes počet konfigurací  
3. Použiji instanci Vrcholového pokrytí - S = V, C = E, všechno funguje.
<{/ForumPost}>