NP (Komplexitätsklasse)

Eine Sprache ${\displaystyle L}$ ist in ${\displaystyle {\text{NP}}}$, falls es eine nichtdeterministische Turingmaschine ${\displaystyle M}$ und ein Polynom ${\displaystyle p}$ gibt, sodass gilt:

• Bei Eingabe von ${\displaystyle x}$ hält ${\displaystyle M}$ nach höchstens ${\displaystyle p(|x|)}$ Schritten (jeder Lauf von ${\displaystyle M}$ auf ${\displaystyle x}$ hat also maximal Länge ${\displaystyle p(|x|)}$).
• ${\displaystyle x\in L}$ genau dann, wenn es mindestens einen akzeptierenden Lauf von ${\displaystyle M}$ auf ${\displaystyle x}$ gibt.

Mit anderen Worten ist ${\displaystyle L\in {\text{NP}}}$ genau dann, wenn es einen polynomiell rechenzeitbeschränkten Verifikator ${\displaystyle M}$ für alle Wörter aus ${\displaystyle L}$ mit ${\displaystyle L(M)=L}$ gibt.

Eine Sprache L ist in NP, falls es eine Relation ${\displaystyle R_{L}\subseteq \{0,1\}^{*}\times \{0,1\}^{*}}$ und ein Polynom p gibt, sodass gilt:

• ${\displaystyle R_{L}}$ wird von einer deterministischen und polynomiell zeitbeschränkten Turingmaschine erkannt, und
• x ∈ L genau dann, wenn es y gibt mit |y| ≤ p(|x|) und ${\displaystyle (x,y)\in R_{L}}$.

Hierbei wird y auch Zertifikat von x genannt, und, im Wahrheitsfall, ein „Beweis“ (proof) oder ein „Zeuge“ (witness) für x, daher auch der (englische) Name „witness relation“ für die Relation ${\displaystyle R_{L}}$.

Gibt es eine NTM M, die L erkennt, so gibt es zu jedem x ∈ L eine akzeptierende Rechnung von M, welche sich in einen String ${\displaystyle \alpha _{M}(x)}$ kodieren lässt. Die Relation ${\displaystyle R_{L}}$ ist dann ${\displaystyle R_{L}=(x,\alpha _{M}(x))}$ für alle x ∈ L und erfüllt die obigen Eigenschaften, denn die akzeptierende Rechnung ist polynomiell in der Länge von x beschränkt und kann deterministisch in polynomieller Zeit überprüft werden.

Gibt es umgekehrt eine Relation ${\displaystyle R_{L}}$ nach obiger Definition, so kann eine NTM M konstruiert werden, die ein entsprechendes y zunächst nichtdeterministisch rät, und dann mittels einer DTM für ${\displaystyle R_{L}}$ überprüft, ob ${\displaystyle (x,y)\in R_{L}}$, also x ∈ L.