Zk 20.1.2016

Zkouskova pisemka, verze A

1. Ukazte, ze nasledujici problem neni algoritmicky rozhodnutelny. Rozhodnete, zda je castecne rozhodnutelny. Sve rozhodnuti zduvodnete.

Pouziti druhe pasky
Instance: Dvoupaskovy Turinguv stroj M (dany svym kodem)
Otazka: Existuje vstup x takovy, ze M zapise nejaky znak na druhou pasku pri vypoctu nad vstupem x?

1. Rozhodnete, zda plati:
   $$NSPACE(\sqrt{n}) \subset SPACE(n \log n)$$
   Mozne odpovedi jsou ano/ne/neni znamo. Sve rozhodnuti zduvodnete.

2. S pomoci nektereho z problemu Kachlikovani, Splnitelnost, 3-Splnitelnost, Vrcholove pokryti, Trojrozmerne parovani, Hamiltonovska kruznice, Obchodni cestujici nebo Loupeznici ukazte, ze nasledujici problem je NP-uplny:

Nejvetsi spolecny podgraf
Instance: Grafy $G_1 = (V_1, E_1)$ a $G_2 = (V_2, E_2)$, prirozene cislo $k \ge 0$
Otazka: Existuji mnoziny hran $E'_1 \subseteq E_1$ a $E'_2 \subseteq E_2$, $|E_1'| = |E_2'| \ge k$, pro nez jsou grafy $G_1 = (V_1, E_1')$ a $G_2 = (V_2, E_2')$ izomorfni (tj. stejne az na prejmenovani vrcholu)?