NP (Komplexitätsklasse)
In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.
Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denen es für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können. Es kann aber aufwändig sein, einen solchen Beweis zu finden. Alternativ kann man also NP beschreiben als die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine (NTM) in Polynomialzeit bezüglich der Eingabelänge gelöst werden können. Wenn ein Rechenzweig der NTM einen Beweis findet und erfolgreich überprüft, dann akzeptiert die die Eingabe, und die Antwort ist „Ja“.
Besonders interessant sind die NP-vollständigen Probleme. Das sind die Probleme in NP, auf die jedes andere Problem in NP polynomiell reduziert werden kann und die somit die schwierigsten Probleme in NP darstellen. NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern im schlechtesten Fall (für die schwierigsten Probleminstanzen) exponentiellen Rechenaufwand, und es wird vermutet, dass es keine Algorithmen gibt, die alle Probleminstanzen in polynomieller Zeit lösen. Die Bestätigung oder Widerlegung dieser Vermutung ist das P-NP-Problem, eines der wichtigsten offenen Probleme der Informatik. Das vielleicht bekannteste NP-vollständige Problem ist das Problem des Handlungsreisenden in seiner Entscheidungsversion. Dieses fragt danach, ob durch gegebene Städte eine Rundreise existiert, deren Länge eine gegebene Grenze nicht überschreitet.
Gelegentlich wird NP fälschlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Die Klasse NP definiert aber lediglich eine obere Schranke für die Komplexität der enthaltenen Probleme und enthält auch alle durch eine deterministische Maschine in Polynomialzeit lösbaren Probleme. Richtig ist, dass für NP-vollständige Probleme (und einige weitere in NP) nicht bekannt ist, ob sie deterministisch in Polynomialzeit lösbar sind; man vermutet, dass dies nicht der Fall ist.