Informatik

Was ist die Komplexitätsklasse NP?

$NP$ enthält Entscheidungsprobleme, deren Ja-Zertifikate in polynomieller Zeit überprüfbar sind.

Äquivalent: lösbar durch eine nichtdeterministische Turingmaschine in polynomieller Zeit.