NP-Schwere

Die Komplexitätstheorie, ein Teilgebiet der theoretischen Informatik, beschäftigt sich mit der Klassifizierung von Problemen. Eine wichtige Problemklasse ist die Komplexitätsklasse NP, die Klasse aller Entscheidungsprobleme, für die eine gefundene Lösung effizient überprüft werden kann. Dabei steht NP für Nichtdeterministische Polynomialzeit – es gibt also eine nichtdeterministische Turingmaschine, die das Problem in Polynomialzeit lösen kann. NP-Schwere bzw. NP-Härte (Fehlübersetzung des englischen NP-hard), bezeichnet eine Eigenschaft eines Problems. Ein NP-schweres Problem ist mindestens so „schwer“ wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem löst, benutzt werden kann, um alle Probleme in NP zu lösen.