# [Zk] 4.2.2011

<{ForumPost(poster="nix21", timestamp=2011-02-04 17:04:43)}>
Reseni:  
1) Neni Rekurzivni z Riceho vety (stacilo rict, ze to neni trivialni mnozina). S je ale RS (je domenou CRF f(x):=PI(m<x,s>\[fi<sub>e,s</sub>(x) = 0])  
2) Viz dukaz 1-uplnosti K, kde misto e stacilo vzit Goedelovo cislo funkce f(x) z predchoziho prikladu  
3) TS, ktery na vstup pusti M<sub>A</sub>, po jeho skonceni smazat pasku a vratit bud kladnou (v pripade ze M<sub>A</sub> prijal) nebo zapornou (v pripade ze neprijal) instanci B. Tyto instance ze zadani urcite existuju a plati tedy, ze TS (ktery je urcite polynomialni, protoze M<sub>A</sub> je polynomialni ze zadani) prevadi instanci A na instanci B. Tedy: x je z A <=> f<sub>M</sub>(x) je z B  
4) Trivialne prevodem z 3DM: C := { {m<sub>w</sub>, m<sub>x</sub>, m<sub>y</sub>} | m je z M}; k = q. Pokud C obsahuje k disjunktnich podmnozin, jsou tyto (prevedene na trojce) soucasti perfektniho parovani v 3DM  
5) Prevest na batoh: A - stejna jako v zadani; vahova funkce - stejna jako v zadani; cenova funkce - konstantni (napr. same jednicky); B = soucet vsech vah / 2. Pak na tomto spustit polynomialni algoritmus pro batoh.  
  
Tot vse.

*Attachments:*

- *[2011_02_04_Verze_F.pdf](/Forum%20archiv/Attachments/3462_56013b580f83baf6a49ffa0a60e2a548)*

<{/ForumPost}>