NP definert ved formelle språk

Et språk $L$ (altså et problem) tilhører NP dersom det eksisterer en polynomisk verifikasjonsalgoritme $A(x,y)$, og en konstant $c$ s.a

$$L=\{x\in \{0,1{\}}^{\ast }:\text{det eksisterer et sertifikat}y\text{der}|y|=O(|x{|}^c)\text{ slik at A(x,y)=1}\}$$