[Zk] Kučera 3. 2. 2017

[Zk] Kučera 3. 2. 2017

Příspěvekod Pecivaal » 4. 2. 2017 10:23

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

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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník