# Zk 20.1.2016

<{ForumPost(poster="ntin", timestamp=2016-01-20 17:56:54)}>
**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.

1. 
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)?


<{/ForumPost}>