od nix21 » 4. 2. 2011 17:04
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>[fie,s(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 MA, po jeho skonceni smazat pasku a vratit bud kladnou (v pripade ze MA 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 MA je polynomialni ze zadani) prevadi instanci A na instanci B. Tedy: x je z A <=> fM(x) je z B
4) Trivialne prevodem z 3DM: C := { {mw, mx, my} | 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.
- Přílohy
-
- 2011_02_04_Verze_F.pdf
- (393.02 KiB) Staženo 456 x
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.