Zk 4.2.2014

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₁, Q₂, ž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ý.