„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
|||
| 173. sor: | 173. sor: | ||
===7. Feladat=== | ===7. Feladat=== | ||
Létezik-e olyan X eldöntési probléma, amire X <big>∉</big> NP és X <big>≺</big> SAT egyszerre fennáll? | Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll? | ||
{{Rejtett | {{Rejtett | ||
| 199. sor: | 199. sor: | ||
Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. <br><br> | Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. <br><br> | ||
<br><br> | <big>'''(''Nem kérdezték, csak kieg.'') Karp-redukció?'''<br><br></big> | ||
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. <br><br> | |||
Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. <br><br> | |||
<big>'''(''Nem kérdezték, csak kieg.'') SAT probléma? '''<br><br></big> | <big>'''(''Nem kérdezték, csak kieg.'') SAT probléma? '''<br><br></big> | ||