Stránka 1 z 1

Zk 4.2.2014

Napsal: 5. 2. 2015 01:48
od Michal Lašan
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 Q1, Q2, ž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ý.