NP (Komplexitätsklasse)

Der Begriff NP 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, deren Lösung von einer deterministischen Turingmaschine in polynomialer Zeit verifiziert werden können.

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 die jede Stadt nur einmal besucht 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 kann. 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.

Siehe auch: P/NP-Problem