Klasse NP (Guess and Check)

Eine Sprache $L$ ist in NP, wenn es ein Polynom $p$ und eine polynomiell zeitbeschränkte DTM $M$ gibt, sodass für jedes $x$ gilt:

x \in L \Leftrightarrow \exists u \in Σ^{p (| x |)} : ⟨ x, u ⟩ \in T (M)

Das Wort $u$ heißt Zertifikat (oder Zeuge). NP modelliert Probleme, deren Lösungen effizient verifiziert werden können.