NP-Schwere - LinkFang.de





NP-Schwere


NP-Schwere bezeichnet eine Eigenschaft eines komplexitätstheoretischen Problems.

Die Komplexitätstheorie, ein Teilgebiet der theoretischen Informatik, beschäftigt sich mit der Klassifizierung von Problemen bezüglich ihrer Komplexität. Eine wichtige Problemklasse ist die Komplexitätsklasse NP, die Klasse aller Entscheidungsprobleme, für die eine gefundene Lösung effizient überprüft werden kann. Dabei steht NP für nichtdeterministische Polynomialzeit. Ein NP-schweres Problem ist dabei mindestens so „schwer“ wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem löst, mithilfe einer Reduktion benutzt werden kann, um alle Probleme in NP zu lösen.

Der umgangssprachlich auftretende Begriff NP-Härte ist eine Fehlübersetzung des englischen NP-hard.

Intuition

Um die Schwere von Problemen zu vergleichen, werden in der theoretischen Informatik Problemreduktionen benutzt. Ein Problem heißt reduzierbar auf ein anderes, wenn jeder Algorithmus, der das zweite Problem löst, auch verwendet werden kann, um das erste zu lösen. Beispielsweise ist das Quadrieren einer Zahl reduzierbar auf die Multiplikation zweier Zahlen, denn jeder Algorithmus, der zwei Zahlen multiplizieren kann, kann auch eine Zahl quadrieren (indem er sie mit sich selbst multipliziert). Multiplizieren ist also in diesem Sinne mindestens so schwer wie Quadrieren. Bei der Reduktion ist wichtig, dass sie effizient geschieht. In der Komplexitätstheorie wird Effizienz durch die Forderung formalisiert, dass die Anzahl der Rechenschritte, die die Reduktion durchführt, durch ein Polynom in der Eingabelänge begrenzt wird; eine solche Reduktion heißt Polynomialzeitreduktion.

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 satisfiability). Das Problem SAT ist also ein schwerstes Problem in NP (Satz von Cook). Es ist allerdings nicht das schwerste Problem, denn Richard M. Karp zeigte, dass es in NP Probleme gibt, auf die SAT reduziert werden kann, die also genauso schwer sind wie SAT. Diese schwersten Probleme in NP werden NP-vollständig genannt und alle Probleme, die mindestens so schwer sind wie sie, 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 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:

  1. führe zuerst die Reduktion auf [math]L'[/math] aus und
  2. 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ä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.

Literatur


Kategorien: Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/NP-Schwere (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.