Hogyan alakítható át egy polinomiális időellenőrző ekvivalens, nem determinisztikus Turing-géppé?
A polinomiális időellenőrző átalakítható egy ekvivalens, nem determinisztikus Turing-géppé, ha olyan gépet készítünk, amely képes kitalálni a bizonyítási bizonyítványt, és azt polinomiális időben ellenőrizni. Ez az átalakítás a nem-determinisztikus számítási koncepción alapul, amely lehetővé teszi a gép számára, hogy az összes lehetséges utat egyszerre fedezze fel.
Ennek az átalakításnak a megértéséhez először határozzuk meg, mi az a polinomiális időellenőrző. A számítási komplexitás elméletében a polinomiális időellenőrző egy determinisztikus Turing-gép, amely képes igazolni egy döntési probléma megoldásának helyességét polinomiális időben. Két bevitelt igényel: a problémapéldányt és egy bizonyítási tanúsítványt, és meghatározza, hogy a tanúsítvány érvényes bizonyíték-e az adott példányra.
Most, hogy egy polinomiális időellenőrzőt egy ekvivalens, nem determinisztikus Turing-géppé alakítsunk át, figyelembe kell vennünk a nem determinisztikus számítás tulajdonságait. Egy nem determinisztikus Turing-gépben minden lépésben a gép több állapotban is lehet, és egyszerre több állapotba is át tud lépni. Ez lehetővé teszi a gép számára, hogy az összes lehetséges számítási utat párhuzamosan fedezze fel.
A hitelesítő konvertálásához összeállíthatunk egy nem determinisztikus Turing-gépet, amely kitalálja a bizonyító tanúsítványt, majd az összes lehetséges útvonalon szimulálja a hitelesítőt. Ha valamelyik útvonal elfogadja, akkor a nem determinisztikus gép elfogadja. Ellenkező esetben elutasítja.
Illusztráljuk ezt egy példával. Tegyük fel, hogy van egy polinomiális időellenőrzőnk a gráf színezésének problémájára. Az ellenőrző bemenetként egy gráfot és annak csúcsainak színezését veszi fel, és ellenőrzi, hogy a színezés érvényes-e úgy, hogy ellenőrzi, hogy egyetlen szomszédos csúcs sem azonos színű.
Ahhoz, hogy ezt a hitelesítőt nem-determinisztikus Turing-géppé alakítsuk, összeállítunk egy gépet, amely kitalálja a színezést, majd szimulálja az ellenőrzőt az összes lehetséges színezésen egyszerre. Ha bármelyik színezés eleget tesz a színezési megkötéseknek, akkor a nem-determinisztikus gép elfogadja. Ellenkező esetben elutasítja.
Ebben a példában a nem determinisztikus gép úgy találja ki a színezést, hogy párhuzamosan rendel színeket a csúcsokhoz. Ezután szimulálja az ellenőrzőt az egyes lehetséges színezéseken, és ellenőrzi, hogy a színezés érvényes-e. Ha valamelyik szimuláció elfogadja, akkor a nem determinisztikus gép is elfogadja.
Ezzel az átalakítással láthatjuk, hogy egy polinomiális időellenőrző átalakítható egy ekvivalens, nem determinisztikus Turing-géppé. Ez az átalakítás lehetővé teszi számunkra, hogy elemezzük az NP (nem determinisztikus polinomiális idő) osztály problémáinak összetettségét, figyelembe véve a polinomiális időellenőrzőket.
Egy polinomiális időellenőrző átalakítható egy ekvivalens, nem determinisztikus Turing-géppé, ha olyan gépet készítünk, amely kitalálja a bizonyítási tanúsítványt, és egyidejűleg minden lehetséges útvonalon ellenőrzi. Ez az átalakítás lehetővé teszi számunkra, hogy elemezzük az NP osztály problémáinak összetettségét.
További friss kérdések és válaszok ezzel kapcsolatban Bonyolultság:
- A PSPACE osztály nem egyenlő az EXPSPACE osztállyal?
- A P komplexitási osztály a PSPACE osztály részhalmaza?
- Bebizonyíthatjuk-e, hogy az Np és a P osztály azonos, ha hatékony polinomiális megoldást találunk bármely NP teljes feladatra egy determinisztikus TM-en?
- Egyenlő lehet az NP osztály az EXPTIME osztállyal?
- Vannak olyan problémák a PSPACE-ban, amelyekre nincs ismert NP algoritmus?
- Lehet egy SAT probléma NP teljes probléma?
- Lehet-e egy probléma NP komplexitási osztályban, ha van egy nem determinisztikus turinggép, amely polinomiális időben megoldja
- Az NP azon nyelvek osztálya, amelyek polinomiális időellenőrzőkkel rendelkeznek
- P és NP valójában ugyanaz a komplexitási osztály?
- Minden környezetfüggetlen nyelv a P komplexitási osztályban?
További kérdések és válaszok a Complexity oldalon