„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 171. sor: | 171. sor: | ||
|szöveg= | |szöveg= | ||
'''(''Nem kérdezték, csak kieg.'') NP osztály?'''<br><br> | <big>'''(''Nem kérdezték, csak kieg.'') NP osztály?'''<br><br></big> | ||
<br> | <br> | ||
| 187. sor: | 187. sor: | ||
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> | 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> | |||
<br><br> | <br><br> | ||
'''(''Nem kérdezték, csak kieg.'') SAT probléma? '''<br><br> | <big>'''(''Nem kérdezték, csak kieg.'') SAT probléma? '''<br><br></big> | ||
todo <br><br> | todo <br><br> | ||
'''A feladat megoldása: '''<br><br> | <big>'''A feladat megoldása: '''<br><br></big> | ||
todo <br><br> | todo <br><br> | ||