Quelltext der Seite NP-Schwere

[[Datei:P np np-complete np-hard.svg|miniatur|[[Mengendiagramm]] der möglichen Beziehungen zwischen [[P (Komplexitätsklasse)|P]], [[NP (Komplexitätsklasse)|NP]] und den Mengen der NP-schweren und [[NP-Vollständigkeit|NP-vollständigen]] Probleme. Zu beachten ist, dass auf der rechten Seite die leere Sprache und ihr Komplement außen vor gelassen werden (beide sind zwar in P und NP, aber nicht NP-schwer).]]
'''NP-Schwere''' bezeichnet die Eigenschaft eines algorithmischen [[Problem]]s, mindestens so schwer lösbar zu sein wie die Probleme der [[NP (Komplexitätsklasse)|Klasse NP]].

Die [[Komplexitätstheorie]], ein Teilgebiet der [[Theoretische Informatik|theoretischen Informatik]], beschäftigt sich mit der Klassifizierung von Problemen bezüglich ihrer Komplexität, d.&nbsp;h. der algorithmischen Schwierigkeit, sie zu lösen. Eine wichtige Problemklasse ist die Komplexitätsklasse NP, die Klasse der Probleme, die mit einer [[Nichtdeterministische Turingmaschine|nichtdeterministischen Turingmaschine]] in [[Polynomialzeit]] gelöst werden können. Anschaulich ist NP die Klasse der [[Entscheidungsproblem|Entscheidungsprobleme]], für die eine gegebene (z.&nbsp;B. geratene) Lösung effizient überprüft werden kann. Ein NP-schweres Problem ist nun mindestens so „schwer“ wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem effizient (also deterministisch in Polynomialzeit) löst, mithilfe einer [[Polynomialzeitreduktion]] genutzt werden kann, um ein beliebiges Problem in NP effizient zu lösen.

Der umgangssprachlich auftretende Begriff '''NP-Härte''' ist eine [[Falscher Freund|Fehlübersetzung]] des [[Englische Sprache|englischen]] ''NP-hard''.

== Intuition ==

Um die Schwere von Problemen zu vergleichen, werden in der theoretischen Informatik Problemreduktionen benutzt. Ein Problem A heißt ''[[Reduktion (theoretische Informatik)|reduzierbar]]'' auf ein anderes Problem B, wenn jeder Algorithmus, der B löst, auch verwendet werden kann, um A zu lösen, indem man eine Probleminstanz von A umrechnet in eine Instanz von B und diese anschließend löst.

Will man durch Reduktionen Aussagen über die Effizienz von Problemen machen, ist die Effizienz der Reduktion ebenfalls wichtig. Wird die Anzahl der Rechenschritte einer Reduktion in Abhängigkeit von der Eingabelänge durch ein Polynom (und nicht etwa durch eine Exponentialfunktion) beschrieben, dann wird diese Reduktion als [[Polynomialzeitreduktion]] bezeichnet. Kann nun ein Problem 1 durch eine Polynomialzeitreduktion in ein Problem 2 überführt werden, dessen Aufwand ebenfalls polynomial von der Eingabe abhängt, so kann Problem 1 selbst in [[Polynomialzeit]] gelöst werden.

Anfang der 1970er Jahre zeigten [[Stephen A. Cook]] und [[Leonid Levin]] unabhängig voneinander, dass es in NP ein Problem gibt, auf das alle anderen Probleme in NP in Polynomialzeit reduziert werden können: das [[Erfüllbarkeitsproblem der Aussagenlogik]] (SAT, von englisch ''{{lang|en|satisfiability}}''). Das Problem SAT ist also ein schwerstes Problem in NP ([[Satz von Cook]]). Es ist allerdings nicht ''das'' einzige schwerste Problem, denn [[Richard M. Karp]] zeigte, dass es in NP [[Karps 21 NP-vollständige Probleme|Probleme gibt, auf die SAT reduziert werden kann]], die also genauso schwer sind wie SAT. Diese schwersten Probleme in NP werden [[NP-Vollständigkeit|NP-vollständig]] genannt. Alle Probleme, auch solche außerhalb von NP, die mindestens so schwer sind wie sie (auf die also SAT in Polynomialzeit reduziert werden kann), heißen NP-schwer.

== Definition ==

Sei <math>L' \subseteq \Sigma^*</math> eine formale Sprache. <math>L'</math> heißt dann ''NP-schwer'', wenn gilt:

<math>\forall \, L \in {\rm NP} : L \preceq_{\rm p} L'</math> (Alle <math>L</math> aus NP sind [[Polynomialzeitreduktion|polynomiell reduzierbar]] auf <math>L'</math>.)

Dies bedeutet, dass <math>L'</math> mindestens so schwer wie jedes beliebige Problem aus NP ist. Diese intuitive Deutung wird gerechtfertigt durch die Tatsache, dass sich mit einem Algorithmus <math>A</math>, der <math>L'</math> in [[Polynomialzeit]] löst, für jedes Problem aus NP ebenfalls ein polynomialer Algorithmus konstruieren ließe:
# führe zuerst die Reduktion auf <math>L'</math> aus und
# anschließend Algorithmus <math>A</math>.

<math>L'</math> selbst kann jedoch auch schwerer sein. Insbesondere muss <math>L'</math> nicht notwendigerweise in NP liegen (liegt <math>L'</math> jedoch zusätzlich in NP, so heißt <math>L'</math> [[NP-Vollständigkeit|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 [[Turingmaschine]]n. 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.

== Literatur ==

* {{Literatur
 | Autor=Michael R. Garey und David S. Johnson
 | Titel=Computers and Intractability
 | TitelErg=A Guide to the Theory of NP-Completeness
 | Verlag=W. H. Freeman and Company
 | Ort=New York
 | Jahr=1979
 | ISBN=0-7167-1045-5
 | Kapitel=Kapitel 5: NP-Hardness
}}


[[Kategorie:Komplexitätstheorie|Npschwere]]

[[he:NP (מחלקת סיבוכיות)#NP-קושי ובעיות NP-שלמות]]