NP-Schwere

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)
Begründung: Ursprünglich allgemeiner QS-Antrag einer IP: Der Artikel sei unverständlich, der englische Artikel sei besser. Antragsteller hat Recht, der Artikel beschränkt sich im Wesentlichen auf Formalia und Fachbegriffe und besteht nicht den Laientest - --Mussklprozz 12:23, 28. Sep. 2010 (CEST)

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. Ein NP-hartes Problem ist mindestens so „schwer“ wie jedes Problem aus der Komplexitätsklasse NP. Formal heißt das, dass alle Probleme aus NP durch einen polynomiellen Algorithmus auf das betrachtete Problem reduziert werden können.

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.