NP

Die Klasse NP enthält alle Probleme,
die von einer nicht-deterministischen Turingmaschine
in polynomieller Zeit $p(n)$ gelöst werden können.

Äquivalente Charakterisierung:

Ein Problem liegt in NP, wenn

1. die Größe der Lösung für eine Eingabe der Größe $n$ polynomiell beschränkt ist, und
2. eine gegebene Lösung in Polynomialzeit verifiziert werden kann.

Interpretation:
Wir können eine Lösung „raten“ und in polynomieller Zeit überprüfen, ob sie korrekt ist.

Beispiel:
SAT ∈ NP.