# [Zk] Kučera 3. 2. 2017

<{ForumPost(poster="Pecivaal", timestamp=2017-02-04 10:23:39)}>


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
    1. pro x vygeneruj všechny cyklické posuny
    1. simuluj M na všech posunech, omezíme počet kroků
    1. pokud M přijme všechny, přijmi
    1. postupně zvyšujeme **délku x** a **limit na počet kroků**
1.  plyne z $NTIME(f(n)) \subseteq SPACE(f(n))$ a deterministické prostorové hierarchie
1.  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](/Forum%20archiv/Attachments/6785_1791ae94c7c80d10bd920433d8c1a978)*

<{/ForumPost}>