Klasse NP

Die Klasse NP (nondeterministic polynomial time) ist die Vereinigung aller polynomiellen NTIME-Klassen:

N P = ⋃_{k \geq 1} N T I M E (n^{k})

Alternative Definition ("Guess and Check"):
Eine Sprache $L$ ist in NP, genau dann wenn es eine deterministische Turingmaschine $V$ (Verifizierer) und ein Polynom $p$ gibt, sodass für alle $x \in Σ^{*}$ gilt:

x \in L \Leftrightarrow \exists c \in Σ^{*} mit | c | \leq p (| x |) : V (x, c) akzeptiert

Hierbei nennt man $c$ das Zertifikat (oder den Zeugen).