Turing-gépek, a P és NP nyelvosztály

Definíció: (Turing-gép)

Turing-gép tartalmaz két szalagot (amelyek mezõknek egy-egy sorozatát tartalmazza), egy inputszalagot (olvasó szalag, amelynek csak véges része elérhetõ számunkra, akkora, amekkorán a konkrét input elfér) és egy munkaszalagot (író-olvasó szalag, amely mindkét irányban végtelen).
A szalagok mezõi egy-egy karaktert tartalmaznak egy véges ábc-bõl. A véges ábc-nek van egy speciális eleme ``blank'', amely az üres mezõt jelöli.
A Turing-gép ezenkívül tartalmaz egy fejet, amely a két szalag egy-egy mezõje felett helyezkedik el (mint egy szemen keresztül a fej látja ezen két mezõ tartalmát) és egy véges állapothalmazból (amelynek START, ELFOGAD, ELVET három kitüntetett eleme) vett elemben mint saját állapotban van.
A gép konfigurációja a két szalag tartalma, a két szalag azon egy-egymezõje, amely felett a fej áll és a fej állapota.
A konfigurációból a fej látja a két elért mezõ tartalmát és a saját állapotát. Ennek függvényében a konfigurációt megváltoztathatja: (i) A munkaszalag fej alatti mezõjének tartalmát megváltoztathatja, (ii) A saját állapotát megváltoztathatja, (iii) A két fejének helyzetét (egymástól függetlenül) megváltoztathatja: egyet balra, vagy egyet jobbra léptetheti (illetve maradhat ott ahol volt). A fenti változtatást egy függvénnyel írjuk le. Ezen függvény szerint a gép egy konfigurációból egy újabb konfigurációt képez.
Ha az inputszalag tartalma az input, a munkaszalagé a csupa blank sorozat, a két fej az input elején, illetve a munka szalag tetszõleges mezõje felett van, akkor a gép a kiinduló konfigurációban van.
A fentiek alapján ebbõl egy konfigurációsorozatot definiál, ez a gép futása.
Ha az elsõ alkalom, amikor a gép ELFOGAD vagy ELVET állapotba kerül az ELFOGAD állapot, akkor a gép elfogadja az inputot. Ha az elsõ alkalom, amikor a gép ELFOGAD vagy ELVET állapotba kerül az ELVET állapot, akkor a gép elveti az inputot. Ha a gép sohasem kerül az ELFOGAD vagy ELVET állapotba, akkor a gép futása végtelen és az inputot elveti.
Az elfogadott inputok halmaza a gép által elfogadott nyelv.

Definíció: Egy M Turing-gép i inputon történõ futásának hossza legyen T(M,i). Legyen T(M,n) az n hosszú i inputok esetén a T(M,i) számok maximuma. T(f(n)) legyen azon L nyelvek osztálya, amelyekhez van olyan M Turing-gép, hogy az M által elfogadot nyelv L legyen és T(M,n)<=f(n). Legyen P a T(b.n^a) nyelvosztályok uniója, ahol a és b a természetes számokon fut keresztül.

Példa: PÁROSÍTÁS nyelv a P nyelvosztály eleme. Ennek igazolásához, azt kell észrevenni, hogy az Edmonds-algoritmus Turing-gépen kódolható és futási ideje n hosszú input esetén polinomiális lesz n-ben.

Definíció: Egy nemdeterminisztikus Turing-gép a Turing-gép egy változata: Az input- és munkaszalag mellett egy csak olvasó bizonyítás szalag is van. Ennek megfelelõen a gép definíció és futása természetes módon módosítható. Egy i inputot akkor és csak akkor fogad el a gép, ha a bizonyítás szalagra írható olyan b jelsorozat, amleyre a gép futása elfogadó.

Definíció: Egy L nyelv az NT(f(n)) nyelvosztályba esik, ha van olyan nemdeterminisztikus M Turing-gép, hogy M az L nyelvet fogadja el, és minden n hosszú inputra és minden bizonyításszalag-tartalomra f(n)-nel felülrõl becsülhetõ a futása. Legyen NP a NT(b.n^a) nyelvosztályok uniója, ahol a és b a természetes számokon fut keresztül.

Példa: SZÍNEZÉS az NP nyelvosztály eleme. A (H,k) input esetén a bizonyításszalagra írjunk fel egy H egy tetszõleges k színezését. A gép ellenõrizze ezt és azt, hogy ez jó színezés-e. Ha igen elfogad, ha nem elvet.

Példa: HAMILTON az NP nyelvosztály eleme. H input esetén a bizonyításszalagra írjuk fel H csúcsainak egy sorrendjét. A gép ellenõrizze, hogy tényleg egy permutációról van-e szó, a sorban egymás mellett álló csúcsok összekötöttek-e, illetve az elsõ és utolsó csúcs összekötött-e. Ha igen, akkor elfogad, különben elvet.

Példa: FÜGGETLEN az NP nyelvosztály egy eleme. (H,k) input esetén a bizonyításszalag tartalma legyen k csúcs. A gép ellenõrizze ezt és azt, hogy a felírt csúcsok között halad-e él.

Nyilvánvaló, hogy P része az NP nyelvosztálynak. Nem ismert, hogy például a SZÍNEZÉS nyelv P-ben van-e. Elképzelhetõ, hogy P=NP. Ennek cáfolata (amit sejtésként a matematikusok széles körben elfogadnak), azonban jelenleg meghaladja tudásunkat.