Zk 29.1.2014

$$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).