Zk 4.2.2014
Napsal: 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 Q1, Q2, ž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ý.
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í:
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ý.