2.5. NP nyelvosztály

A determinisztikus Turing-gép akkor fogad el egy inputot, ha azzal indítva leáll. A nemdeterminisztikus Turing-gép ugyanannál az inputnál más és más lépéssorozatokat hajthat végre, egyes esetekben megáll, máskor pedig nem. Ha van olyan számítási eljárás, melyben a Turing-gép megáll, akkor azt a nemdeterminisztikus Turing-gép elfogadja az inputot.

A T nemdeterminisztikus Turing-gép t(n) időkorlátos, ha n hosszú inputon minden számítási út mentén legfeljebb t(n) lépést téve megáll. NTIME(t(n)) azon nyelvek halmaza, melyek felismerhetőek egy O(t(n)) időkorlátos nemdeterminisztikus Turing-géppel.

Tétel. Egy L nyelv pontosan akkor tartozik az NP nyelvosztályba, ha létezik egy olyan párosokból álló L0 P-beli nyelv, hogy x eleme L-nek akkor és csak akkor, ha (x, y) eleme L0-nek valamely y-ra. Az y-t gyakran x tanújának szokás nevezni.