Zk 29.1.2014

Zk 29.1.2014

Příspěvekod steve-s » 1. 2. 2014 11:06

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
<br />otin{K} \Rightarrow \varphi_x{(x)\uparrow} \Rightarrow x
<br />otin{W_x} \Rightarrow f(x)=\langle{x},x,x\rangle 
<br />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
<br />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
<br />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).
steve-s
 

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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron