od Pecivaal » 4. 2. 2017 10:23
Řešení
- není rozh. - plyne z Riceovy věty (stačí ukázat, že příslušná třída jazyků je netriviální, tj. najít nějaký, který do ní patří, a nějaký, který do ní nepatří)
je část. rozh. - příslušný TS pracuje následovně:
- generuj x s rostoucí délkou
- pro x vygeneruj všechny cyklické posuny
- simuluj M na všech posunech, omezíme počet kroků
- pokud M přijme všechny, přijmi
- postupně zvyšujeme délku x a limit na počet kroků
- plyne z a deterministické prostorové hierarchie
- na tento problém lze převést Hamiltonovskou cestu (stačí nastavit k=2), na který umíme převést Hamiltonovskou kružnici
Pozn.: tady se mu nelíbil převod z kružnice na cestu (pro každou hranu (u,v) vytvoříme instanci Ham. cesty tak, že přidáme "růžky" (listy) k u a v) - tvrdil, že to není polynomiální převod (jak se to dělalo na cviku, netuším). Ale uznal nám to.
[attachment=0]IMG_20170204_100032.jpg[/attachment]
[line][/line]
[b]Řešení[/b]
[list=1]
[*] není rozh. - plyne z Riceovy věty (stačí ukázat, že příslušná třída jazyků je netriviální, tj. najít nějaký, který do ní patří, a nějaký, který do ní nepatří)
je část. rozh. - příslušný TS pracuje následovně:
[list=a]
[*]generuj x s rostoucí délkou
[*]pro x vygeneruj všechny cyklické posuny
[*]simuluj M na všech posunech, omezíme počet kroků
[*]pokud M přijme všechny, přijmi
[*]postupně zvyšujeme [b]délku x[/b] a [b]limit na počet kroků[/b][/list]
[*] plyne z [latex]NTIME(f(n)) \subseteq SPACE(f(n))[/latex] a deterministické prostorové hierarchie
[*] na tento problém lze převést Hamiltonovskou cestu (stačí nastavit k=2), na který umíme převést Hamiltonovskou kružnici
Pozn.: tady se mu nelíbil převod z kružnice na cestu (pro každou hranu (u,v) vytvoříme instanci Ham. cesty tak, že přidáme "růžky" (listy) k [i]u[/i] a[i] v[/i]) - tvrdil, že to není polynomiální převod (jak se to dělalo na cviku, netuším). Ale uznal nám to.[/list]