od steve-s » 1. 2. 2014 11:06
Je rekurzivní? Pokud ne, je rekurzivně spočetná nebo alespoň její doplněk?
Řešení: ukážeme, že
.
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í.
jsou dva netriviální problémy, tj. existuje
a
, totéž platí pro B. Ukažte, že
.
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
nebo
.
Č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).
[latex]S=\{\langle{x},y,z \rangle|z\in{W_x \cup W_y\}[/latex]
Je rekurzivní? Pokud ne, je rekurzivně spočetná nebo alespoň její doplněk?
Řešení: ukážeme, že [latex]K\leq_{m}S[/latex].
[latex]f(x)=\langle{x},x,x\rangle[/latex]
[latex]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)[/latex]
[latex]x
otin{K} \Rightarrow \varphi_x{(x)\uparrow} \Rightarrow x
otin{W_x} \Rightarrow f(x)=\langle{x},x,x\rangle
otin S[/latex]
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í.
[latex]g(\langle{x},y,z\rangle{)} = \mu{s}\[\varphi_{x,s}{(z)\downarrow \vee \varphi_{y,s}{(z)\downarrow\][/latex]
[latex]A,B \in P[/latex] jsou dva netriviální problémy, tj. existuje [latex]x\in{A}[/latex] a [latex]y
otin{A}[/latex], totéž platí pro B. Ukažte, že [latex]A\leq_{m}^{p}B[/latex].
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 [latex]x\in{B}[/latex] nebo [latex]y
otin{B}[/latex].
Č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).