Komplexitätsklasse NP

Probleme aus NP

Ein Entscheidungsproblem aus der Komplexitätsklasse NP kann von einer nichtdeterministischen Turingmaschine in Polynomialzeit gelöst werden, jedoch schafft es die deterministische Turingmaschine dies nicht in Polynomialzeit. Eine deterministische Turingmaschine kann jedoch für Lösungsvorschläge bzgl. Probleme aus NP in Polynomialzeit herausfinden, ob die Lösung richtig oder falsch ist.

Probleme aus NP lassen sich laut vielen theoretischen Informatikern praktisch nicht effizient lösen. Die Algorithmen die uns heutzutage für diese Probleme zur Verfügung stehen erfordern nicht-polynomiellen Aufwand, d.h. exponentiellen Aufwand.