Zk 4.2.2015

Verze F

1. Rozhodněte, zda množina
   S={x| fí_x je konstantní ČRF, tj. (existuje c) (pro každé y) [fí_x(y) ↓ implikuje fí_x(y) rovnáse s vlnovkou c]}
   je rekurzivní, rekurzivně spočetná, doplněk rekurzivně spočetné množiny, nebo nepatří do žádné z těchto kategorií. Svá rozhodnutí zdůvodněte.
   Speciálně funkce, která není definovaná pro žádný vstup, podle této definice konstantní je.

2. Dokažte následující tvrzení. Predikát P(x) je obecně rekurzivní právě tehdy, když existují primitivně rekurzivní predikáty Q₁(x,y) a Q₂(x,y) a platí:
   P(x) právě tehdy, když (existuje y) [Q₁(x,y)] právě tehdy, když (pro každé y) [Q₂(x,y)]

3. S pomocí některého problému probíraného na přednášce (tj, KACHL, SAT, 3SAT, Vrcholové pokrytí, Trojrozměrné párování, Hamiltonovská kružnice, Obchodní cestující nebo Loupežníci) ukažte, že následující problém je NP-úplný:
   Množinové pokrytí
   Instance: Systém množin C konečné množiny prvků, tj C je částí P(S), přirozené číslo k.
   Otázka: Je možné vybrat C', C' je částí C, která obsahuje nejvýš k množin a přitom sjednocení přes C' je S?

↓ je šipka dolů, omlouvám se za to, že neumím latex.
Další termín bude v létě, říkal mi to. Výjimku dá těm, co by chtěli ke státnicím předtím.