# Zk 4.2.2015

<{ForumPost(poster="někdo", timestamp=2015-02-05 01:24:56)}>
Verze F  
  
1.  
Rozhodněte, zda množina  
S={x| fí<sub>x</sub> je konstantní ČRF, tj. (existuje c) (pro každé y) \[fí<sub>x</sub>(y) &darr; implikuje fí<sub>x</sub>(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<sub>1</sub>(x,y) a  Q<sub>2</sub>(x,y) a platí:  
P(x) právě tehdy, když (existuje y) \[Q<sub>1</sub>(x,y)]  právě tehdy, když (pro každé y) \[Q<sub>2</sub>(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?  
  
&darr; 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.
<{/ForumPost}>