[Zk] Kučera 3. 2. 2017

IMG_20170204_100032.jpg

Řešení

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ě:

   1. generuj x s rostoucí délkou

   2. pro x vygeneruj všechny cyklické posuny

   3. simuluj M na všech posunech, omezíme počet kroků

   4. pokud M přijme všechny, přijmi

   5. postupně zvyšujeme délku x a limit na počet kroků

2. plyne z $NTIME(f(n)) \subseteq SPACE(f(n))$ a deterministické prostorové hierarchie

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

Attachments:

• IMG_20170204_100032.jpg