NP-schwer bzw. NP-hart (von englisch NP-hard, abgekürzt für Non-deterministic Polynomial-time hard) ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik. Er dient der Klassifizierung von Problemen, die im Sinne der formalen Theorie besonders aufwändig zu berechnen sind.

Definition

Sei $L\_1\; \backslash sub\; \backslash Sigma^*$, also eine formale Sprache.

$L\_1$ heißt nun NP-schwer, falls $\backslash forall\; L\; \backslash in\; NP\; :\; L\; \backslash le\_P\; L\_1$, also alle $L$ aus NP polynomiell reduzierbar auf $L\_1$ sind.

Dies bedeutet, dass $L\_1$ ein Entscheidungsproblem ist und mindestens so schwer wie jedes beliebige Problem aus NP. Diese intuitive Deutung wird gerechtfertigt durch die Tatsache, dass sich mit einem Algorithmus $A$, der $L\_1$ 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\_1$ aus und
2. anschließend Algorithmus $A$.

$L\_1$ selbst kann jedoch auch schwerer sein. Insbesondere muss $L\_1$ nicht notwendigerweise in NP liegen (liegt $L\_1$ jedoch zusätzlich in NP, so heißt $L\_1$ 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überhinaus liegt das Halteproblem aber selbst nicht in NP, da es überhaupt nicht entscheidbar ist.

Siehe auch

---

• NP-Vollständigkeit

Komplexitätstheorie

NP-hard | NP-hard | NP-קשה | NP困難 | Problem NP-trudny