NP-Schwere
aus Wikipedia, der freien Enzyklopädie
NP-schwer bzw. NP-hart (Fehlübersetzung 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.
[Bearbeiten] Definition
Sei 
, also eine formale Sprache. L1 heißt dann NP-schwer, falls 
, also alle L aus NP polynomiell reduzierbar auf L1 sind.
Dies bedeutet, dass L1 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 L1 in Polynomialzeit löst, für jedes Problem aus NP ebenfalls ein polynomialer Algorithmus konstruieren ließe:
- führe zuerst die Reduktion auf L1 aus und
- anschließend Algorithmus A.
L1 selbst kann jedoch auch schwerer sein. Insbesondere muss L1 nicht notwendigerweise in NP liegen (liegt L1 jedoch zusätzlich in NP, so heißt L1 NP-vollständig).
[Bearbeiten] 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.
