Zk 13.2.2012

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zk 13.2.2012

Re: Zk 13.2.2012

od blabla » 29. 1. 2013 00:46

Pouzitie rice-a by v tomto pripade malo byt celkom priamociare.. S nie je ani prazdna ani neobsahuje indexy vsetkych CRF takze rpiamo z rice-a vyplyva ze nie je rekurzivna.

S je rekurzivne spocetna a to preto, lebo je definicnym oborom funkcie f definovanej ako:
f(<x, y, z>) = \mu<r, s>[\varphi_{x, s}(z) \downarrow \wedge \varphi_{y, r}(z) \downarrow \wedge \varphi_{x, s}(z) \simeq \varphi_{y, r}(z)]

\overline{S} tym padom nemoze byt r.s. lebo S nie je rekurzivna mnozina.

alebo je na to nieco zle?

Re: Zk 13.2.2012

od Sylverling » 22. 2. 2012 17:11

Pro uplnost: prevod ve tretim prikladu se da resit i pres prevod Vertex Cover -> Independent Set -> Set Packing (a jde to hooodne jednoduse).

A ta 1) by sla asi resit i pres Rice, kdyby se predtim nejak sikovne pouzila s-m-n veta, ale kdo by to delal, kdyz to jde lip jinak.

Zk 13.2.2012

od wladik » 13. 2. 2012 19:11

1) Rozhodnout jestli množina S = \{ <x,y,z> |  \varphi_x(z) \downarrow \wedge \varphi_y(z) \downarrow \wedge \varphi_x(z) = \varphi_y(z) \} je rekurzivní, pokud není, tak jestli S nebo \overline{S} je rekurzivně spočetná.

2) Ukažte, že problém Omezený součet podmnožiny je polynomiálně řešitelný:
Instance: Množina n prvků A, s každým prvkem a \in A asociovaná velikost v(a) \in \{ 0,...,n \}, číslo B \leq 0.
Otázka: Existuje množina prvků {A}' \subseteq A pro níž platí, že:
\sum_{a\in{A}'}v(a)= B?

3) NP-úplnost problému Set Packing
Instance: Množina C konečných množin a přirozené číslo k \leq  0
Otázka: Obsahuje C alespoň k po dvou disjunktních množin?

náznaky pro řešení:
1) Riceova věta tady nejde použít, jde o množinu trojic
2) Převodem na batoh
3) pomocí 3DM

Nahoru