Zk 29.1.2014
Napsal: 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).