Zk 29.1.2014

steve-s

Zk 29.1.2014

Příspěvek od steve-s »

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).
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“