NP-Schwere

NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie die Probleme der Klasse NP.

Die Komplexitätstheorie, ein Teilgebiet der theoretischen Informatik, beschäftigt sich mit der Klassifizierung von Problemen bezüglich ihrer Komplexität, d. h. der algorithmischen Schwierigkeit, sie zu lösen. Eine wichtige Problemklasse ist die Komplexitätsklasse NP, die Klasse der Probleme, die mit einer nichtdeterministischen Turingmaschine in Polynomialzeit gelöst werden können. Anschaulich ist NP die Klasse der Entscheidungsprobleme, für die eine gegebene (z. B. geratene) Lösung effizient überprüft werden kann. Ein NP-schweres Problem ist nun mindestens so „schwer“ wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem effizient (also deterministisch in Polynomialzeit) löst, mithilfe einer Polynomialzeitreduktion genutzt werden kann, um ein beliebiges Problem in NP effizient zu lösen.

Der umgangssprachlich auftretende Begriff NP-Härte ist eine Fehlübersetzung des englischen NP-hard.