Kučera 19.1.

Aearsis
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 17. 1. 2017 09:45
Typ studia: Informatika Mgr.

Kučera 19.1.

Příspěvek od Aearsis »

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

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“