od Michal Lašan » 5. 2. 2015 01:48
1.
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
1, Q
2, že platí:
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,
je RS, pretože je určená takýmto predikátom:
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ý.
1. [latex]S = \{e\: |\: (\exists c)(\forall x)(\varphi_e(x)\downarrow \:\Rightarrow \varphi_e(x) = c\}[/latex]
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í:
[latex]P(x) \Leftrightarrow (\exists y)(Q_1(x, y)) \Leftrightarrow (\forall y)(Q_2(x, y))[/latex]
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, [latex]\overline{S}[/latex] je RS, pretože je určená takýmto predikátom:
[latex]\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)\}[/latex]
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ý.