[Zk] Kučera 3. 2. 2017

Pecivaal
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 16. 1. 2014 13:08
Typ studia: Informatika Bc.

[Zk] Kučera 3. 2. 2017

Příspěvek od Pecivaal »

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.
Odpovědět

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