# Zk 29.1.2014

<{ForumPost(poster="steve-s", timestamp=2014-02-01 11:06:54)}>
$$S=\{\langle{x},y,z \rangle|z\in\{W_x \cup W_y\}$$  
Je rekurzivní? Pokud ne, je rekurzivně spočetná nebo alespoň její doplněk?  
  
Řešení: ukážeme, že $K\leq_{m}S$.   
$$f(x)=\langle{x},x,x\rangle$$  
$$x\in{K} \Rightarrow \varphi_x{(x)\downarrow} \Rightarrow x\in{W_x} \Rightarrow f(x)=\langle{x},x,x\rangle \in S (x \in W_x \cup W_x)$$  
$$x
otin{K} \Rightarrow \varphi_x{(x)\uparrow} \Rightarrow x
otin{W_x} \Rightarrow f(x)=\langle{x},x,x\rangle 
otin S$$  
Z toho plyne, že pomocí náležení do S bysme uměli řešit náležení do K (halting problem), tím pádem S není rekurzivní.  
  
$$g(\langle{x},y,z\rangle{)} = \mu{s}[\varphi_{x,s}(z)\downarrow \vee \varphi_{y,s}(z)\downarrow]$$  
  
$A,B \in P$ jsou dva netriviální problémy, tj. existuje $x\in{A}$ a $y
otin{A}$, totéž platí pro B. Ukažte, že $A\leq_{m}^{p}B$.  
Je to polynomiální převoditelnost, takže v naší polynomiální funkci pro převod prostě můžeme spočítat A a podle výsledku vrátit $x\in{B}$ nebo $y
otin{B}$.  
Čekal jsem, že bude ještě potřeba ukázat, jak se najde takové x a y v poly čase (na to by šla možná použít nějaká finta z té kapitoly o #P), ale takhle to stačilo.  
  
Převod byl hitting set (velmi jednoduše z vertex cover).
<{/ForumPost}>