# Zk 4.2.2014

<{ForumPost(poster="Michal Lašan", timestamp=2015-02-05 01:48:04)}>
1. $S = \{e\: |\: (\exists c)(\forall x)(\varphi_e(x)\downarrow \:\Rightarrow \varphi_e(x) = c\}$  
Určiť, či je R, RS alebo doplnok RS.  
  
2. Ukázať, že P(x) je ORF práve vtedy, keď existujú primitívne rekurzívne predikáty Q<sub>1</sub>, Q<sub>2</sub>, že platí:  
$$P(x) \Leftrightarrow (\exists y)(Q_1(x, y)) \Leftrightarrow (\forall y)(Q_2(x, y))$$  
  
3. Ukázať NP-úplnosť:  
S je množina, C je množina podmnožín S, pevne zadané k.   
Existuje podmnožina C taká, že zjednotenie jej prvkov je rovné S?  
  
Riešenia:  
1. Z Ricea nie je R, $\overline{S}$ je RS, pretože je určená takýmto predikátom:  
$$\mu(s, x_1, x_2)(\varphi_{e,s}(x_1)\downarrow \&\: \varphi_{e,s}(x_2)\downarrow\ \&\: \varphi_{e,s}(x_1) 
ot= \varphi_{e,s}(x_2)\}$$  
Z vlastností konečných aproximácií a logických spojok je argument minimalizácie R, preto je predikát RS. S teda nie je RS, lebo podľa Postovej vety by musela byť rekurzívna.  
  
2. Nejako z Postovej vety.  
  
3. Prevodom z vrcholového pokrytia: v S budú všetky hrany v grafe, v C bude pre každý vrchol množina hrán, v ktorých je ten vrchol obsiahnutý.
<{/ForumPost}>