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

Def: P (nyelvosztály) := U TIME (Ui) polinomiális idobonyolultságú Turing géppel felismerheto nyelvek osztálya.
Def.: NTIME (f(n)) (nyelvosztály):={L T Turing gép L-et ismeri fel, T idobonyolultsága (f(n))}

Def.: NSPACE (f(n)) (nyelvosztály):={L T Turing gép L-et ismeri fel, T tárbonyolultsága (f(n))}

TIME (f(n)) (fektetett u vonal )NTIME (f(n))
A polinominális idobonyolultságú turing géppel felismerheto nyelvek osztálya részhalmaza a nemdetermisztikus polinominális idobonyolultságú turing géppel felismertetheto nyelvek osztályának.

Def.: NP (nyelvosztály):= U NTIME (ui)
Az NP nyelvosztály a nem determisztikus polinominális idobonyolultságú Turing géppel felismertetheto nyelvek uniójával egyezik meg.

Mi a viszony NP és P között? P(fektetett u vonal )Np (TIME (ui)(fektett u vonal) NTIME (ui))