NP-Härte

NP-Schwere bzw. NP-Härte (Fehlübersetzung des englischen NP-hard, abgekürzt für Non-deterministic Polynomial-time hard) ist ein Begriff aus dem Bereich der theoretischen Informatik, der zur Klassifizierung von Komplexitätsproblemen dient. Er gibt Aufschluss darüber, ob für alle Probleme aus der Komplexitätsklasse NP jeweils ein polynomieller Algorithmus existiert, der diese auf eine betrachtete formale Sprache reduziert.

Definition

Sei $L' \sub \Sigma^*$ eine formale Sprache. L' heißt dann NP-schwer, wenn gilt:

$\forall \, L \in {\rm NP} : L \preceq_{\rm p} L'$ (Alle L aus NP sind polynomiell reduzierbar auf L'.)

Dies bedeutet, dass L' mindestens so schwer wie jedes beliebige Problem aus NP ist. Diese intuitive Deutung wird gerechtfertigt durch die Tatsache, dass sich mit einem Algorithmus A, der L' in Polynomialzeit löst, für jedes Problem aus NP ebenfalls ein polynomialer Algorithmus konstruieren ließe:

1. führe zuerst die Reduktion auf L' aus und
2. anschließend Algorithmus A.

L' selbst kann jedoch auch schwerer sein. Insbesondere muss L' nicht notwendigerweise in NP liegen (liegt L' jedoch zusätzlich in NP, so heißt L' NP-vollständig).

Beispiel

Ein klassisches Beispiel für ein Problem, das NP-schwer ist und nicht in NP liegt, ist das Halteproblem für Turingmaschinen. Beispielsweise lässt sich das Erfüllbarkeitsproblem auf das Halteproblem reduzieren, indem eine Instanz des Erfüllbarkeitsproblems in eine Turingmaschine transformiert wird, die nacheinander alle möglichen Belegungen durchprobiert und hält, sobald eine erfüllende Belegung gefunden ist, andernfalls jedoch in eine Endlosschleife übergeht. Darüber hinaus liegt das Halteproblem aber selbst nicht in NP, da es überhaupt nicht entscheidbar ist.

Siehe auch

• NP-Vollständigkeit
• Vollständigkeit (Komplexitätstheorie)