Kučera 19.1.

1. Ukažte, že následující problém není algoritmicky rozhodnutelný:
   Pomalejší TS
   Instance: Dva TS M₁ a M₂ zadané svými kódy.
   Otázka: Platí pro každé x ∈ Σ*, že M₁ vykoná při práci nad vstupem x alespoň tolik kroků, kolik jich se vstupem x vykoná M₂?
   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^n²) 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₁ 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.