„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 225. sor: | 225. sor: | ||
|szöveg= | |szöveg= | ||
'''(''Nem kérdezték, csak kieg.'') | <big>'''(''Nem kérdezték, csak kieg.'') Eldöntési probléma osztályok? '''<br><br></big> | ||
'''(''Nem kérdezték, csak kieg.'') | <br> | ||
[[File:bonyolultsag_elmelet.JPG|390px]] | |||
<br> | |||
A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. <br><br> | |||
Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik.<br><br> | |||
A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. <br><br> | |||
Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre (jelenleg) nem ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') <br><br> | |||
A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). <br><br> | |||
Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). <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>'''(''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> | |||
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> | |||
'''(''Nem kérdezték, csak kieg.'') H-út? '''<br><br> | '''(''Nem kérdezték, csak kieg.'') H-út? '''<br><br> | ||