Ř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.