Ha egy algoritmus megold egy problémát, akkor implicite
arra is bizonyítékot szolgáltat, hogy a válasza helyes.Néha ez a bizonyíték sokkal egyszerubb (rövidebb,
áttekinthetobb), mint a bizonyíték megtalálása, azaz az
algoritmus futásának figyelemmel kísérése.Vizsgálhatjuk csupán a bizonyítékot annélkül, hogy
törodnénk vele, hogyan lehet megtalálni. Ha tudjuk, hogy egy feladatra adott bizonyíték helyessége
sem adható meg adott idon (vagy táron) belül, akkor az
algoritmus bonyolultságára is alsó becslést kapunk.Aszerint osztályozva a feladatokat, hogy milyen nehéz a
válaszra a helyességét rábizonyítani, igen érdekes és
Alapveto bonyolultsági osztályokat kapunk!Ez az a gondolat, melyet nem-determinizmusnak
neveznek.

Egy nem-determinisztikus Turing-gép annyiban különbözik
egy determinisztiustól, hogy minden helyzetében több lehet-
Séges lépés is megengedett a vezérloegység állapotának és
a fejek által leolvasott jelek függvényében.

Legális számolásnak nevezzük a gép legális lépéseinek egy
sorozatát.

Muködése: Adott konfigurációból át megy másikba, ha ez az átmenet megfelel annak az átmenetnek, amelyet ez a halmaz tartalmaz : T átmegy a K1-ból a K2-be ha a (qi, bi1, mi1…mik)elem belsö állapotok halmazának és (q, a1…an)és a K1 megfelel a (q,a1…an) –nek K2 pedig a )= (q’,b1, …bk, m1, ….mk).

L nyelv, ha L felismerheto, nemdeterminisztikus Turing géppel, akkor felismerheto determinisztikus Turing géppel is.
Biz: A determinisztikus T.g.-pel szimuláljuk a nemdeterminisztikus T.g. muködését. A determinisztikus Turing gép szalagján tároljuk a nemdeterminisztikus Turing gép azonos szinten levo összes elérheto konfigurációját. Kiindulva az egyetlen kezdo konfigurációból , a következo szinten az összes konfigurációt, ami 1 lépésben elérheto a kezdobol, utána az összes konfigurációt, ami 1 lépésben elérheto ezekbol, és így tovább. Ha elfogadó konfigurációba jutunk, megállunk.
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ó