# Zk 13.2.2012

<{ForumPost(poster="wladik", timestamp=2012-02-13 19:11:02)}>
1) Rozhodnout jestli množina  $S = \{ <x,y,z> |  \varphi_x(z) \downarrow \wedge \varphi_y(z) \downarrow \wedge \varphi_x(z) = \varphi_y(z) \}$ je rekurzivní, pokud není, tak jestli $S$ nebo $\overline{S}$ je rekurzivně spočetná.  
  
2) Ukažte, že problém Omezený součet podmnožiny je polynomiálně řešitelný:  
Instance:  Množina n prvků $A$, s každým prvkem $a \in A$ asociovaná velikost $v(a) \in \{ 0,...,n \}$, číslo $B \leq 0$.  
Otázka: Existuje množina prvků ${A}' \subseteq A$ pro níž platí, že:  
$$\sum_{a\in{A}'}v(a)= B?$$  
  
3) NP-úplnost problému Set Packing  
Instance: Množina C konečných množin a přirozené číslo $k \leq  0$  
Otázka: Obsahuje C alespoň k po dvou disjunktních množin?  
  
náznaky pro řešení:  
1) Riceova věta tady nejde použít, jde o množinu trojic  
2) Převodem na batoh  
3) pomocí 3DM
<{/ForumPost}>

<{ForumPost(poster="Sylverling", timestamp=2012-02-22 17:11:53)}>
Pro uplnost: prevod ve tretim prikladu se da resit i pres prevod Vertex Cover -> Independent Set -> Set Packing (a jde to hooodne jednoduse).  
  
A ta 1) by sla asi resit i pres Rice, kdyby se predtim nejak sikovne pouzila s-m-n veta, ale kdo by to delal, kdyz to jde lip jinak.
<{/ForumPost}>

<{ForumPost(poster="blabla", timestamp=2013-01-29 00:46:34)}>
Pouzitie rice-a by v tomto pripade malo byt celkom priamociare.. S nie je ani prazdna ani neobsahuje indexy vsetkych CRF takze rpiamo z rice-a vyplyva ze nie je rekurzivna.  
  
$S$ je rekurzivne spocetna a to preto, lebo je definicnym oborom funkcie f definovanej ako:  
$$f(<x, y, z>) = \mu<r, s>[\varphi_{x, s}(z) \downarrow \wedge \varphi_{y, r}(z) \downarrow \wedge \varphi_{x, s}(z) \simeq \varphi_{y, r}(z)]$$  
  
$\overline{S}$ tym padom nemoze byt r.s. lebo $S$ nie je rekurzivna mnozina.  
  
alebo je na to nieco zle?
<{/ForumPost}>