od Aearsis » 19. 1. 2017 18:05
1. Ukažte, že následující problém není algoritmicky rozhodnutelný:
Pomalejší TS
Instance: Dva TS M
1 a M
2 zadané svými kódy.
Otázka: Platí pro každé x ∈ Σ*, že M
1 vykoná při práci nad vstupem x alespoň tolik kroků, kolik jich se vstupem x vykoná M
2?
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
taková, že S' obsahuje nejméně jeden prvek z každé množiny v C?
Spoiler:
1. Buď M
1 TS, který se na každém vstupu zacyklí -> Halting problém. Doplněk je částečně rozhodnutelný - NTS uhodne protipříklad.
2.
 \subset TIME(2^{n^2}))
- přes počet konfigurací
3. Použiji instanci Vrcholového pokrytí - S = V, C = E, všechno funguje.
1. Ukažte, že následující problém není algoritmicky rozhodnutelný:
Pomalejší TS
[b]Instance:[/b] Dva TS M[sub]1[/sub] a M[sub]2[/sub] zadané svými kódy.
[b]Otázka:[/b] 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 [i]log[/i] 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
[b]Instance:[/b] Množina S a množina C podmnožin množiny S, přirozené číslo k > 0.
[b]Otázka:[/b] Existuje [latex]S' \subset S, |S'| \leq k[/latex] taková, že S' obsahuje nejméně jeden prvek z každé množiny v C?
[line][/line]
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. [latex]NSPACE(n \log n) \subset TIME(2^{n^2})[/latex] - přes počet konfigurací
3. Použiji instanci Vrcholového pokrytí - S = V, C = E, všechno funguje.