„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 179. sor: | 179. sor: | ||
|szöveg= | |szöveg= | ||
<big>''' | {{Rejtett | ||
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big> | |||
|szöveg= | |||
<big>'''Eldöntési probléma osztályok? '''<br><br></big> | |||
<br> | <br> | ||
| 199. sor: | 202. 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> | ||
<big>''' | <big>'''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> | 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> | ||
| 206. sor: | 209. sor: | ||
Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen.<br><br> | Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen.<br><br> | ||
<big>''' | <big>'''SAT probléma? '''<br><br></big> | ||
todo <br><br> | todo <br><br> | ||
}} | |||
<big>'''A feladat megoldása: '''<br><br></big> | <big>'''A feladat megoldása: '''<br><br></big> | ||