NP (Komplexitätsklasse)
Der Begriff NP (von englisch Non-deterministic Polynomial time) stammt aus der Komplexitätstheorie. Er bezeichnet eine Klasse von Problemen, die von einer nichtdeterministischen Turingmaschine in polynomialer Zeit entschieden werden können.
Es gibt noch eine zweite äquivalente Definition von NP als die Menge aller Probleme, für die es, wenn die Antwort ja lautet, einen entsprechenden Beweis (Zertifikat) gibt, dessen Länge durch ein Polynom in der Länge des Problems beschränkt ist, und der von einer deterministischen Turingmaschine in polynomialer Zeit verifiziert werden kann.
Ein Beispiel ist das Problem des Handlungsreisenden. Gegeben ist eine Menge von Städten, deren paarweise Entfernungen und eine feste Länge L. Frage: Gibt es eine Rundreise, bei der jede Stadt nur einmal besucht wird und deren Gesamtlänge L nicht übersteigt? Offenbar lässt sich hier eine Lösung leicht verifizieren. Bei einer gegebenen Rundreise müssen nur die einzelnen Entfernungen addiert und die Summe mit L verglichen werden.
Häufig wird NP irrtümlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Dies ist aber falsch, da die Menge der in Polynomialzeit deterministisch lösbaren Probleme eine (vermutlich echte) Teilmenge von NP ist. Außerdem gibt es auch Probleme, die nicht in polynomialer Zeit gelöst werden können, bei denen aber nicht einmal die Lösungen in polynomialer Zeit verifiziert werden können. Solche Probleme gehören demnach auch nicht zu NP.
Viele Probleme, die in der Komplexitätsklasse NP liegen, insbesondere die NP-vollständigen, lassen sich vermutlich nicht effizient lösen, da sie exponentiellen Rechenaufwand erfordern.
Beziehung zu anderen Komplexitätsklassen
Die folgenden Beziehungen sind bekannt:
Siehe auch: P/NP-Problem