NP-Schwere

NP-Schwere
QS-Informatik

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.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Schwere Panzerabteilung — Schwere Panzerabteilungen waren bataillonsgroße deutsche Panzerverbände des Zweiten Weltkrieges. Es handelte sich um selbstständige Einheiten, die ausschließlich mit schweren Kampfpanzern der Typen Tiger und Tiger II ausgestattet waren und zur… …   Deutsch Wikipedia

  • Schwere, -messung — Schwere, messung. Die Intensität oder Beschleunigung der Schwere für einen Punkt der Erdoberfläche ist abhängig von dem Ort auf dem Normalsphäroid, der allgemeinen geographischen Lage als Kontinental , Küsten oder Inselpunkt, der topographischen… …   Lexikon der gesamten Technik

  • Schwere Panzer Abteilung 502 — Période 25 mai 1942 – 9 mai 1945 Pays …   Wikipédia en Français

  • Schwere — (Schwerkraft) ist die Resultante aus der Anziehungskraft der Erde und der Zentrifugalkraft infolge der Erddrehung. Ihre Wirkung auf einen relativ zur Erde ruhenden Körper heißt dessen Gewicht und kann für nicht zu ausgedehnte Körper im… …   Lexikon der gesamten Technik

  • Schwere, Schweremessung — Schwere, Schweremessung. – 1901 stellte Helmert die in Bd. 8, S. 15 mitgeteilten Formeln für die normale Schwerkraft γ im Meeresniveau auf. Die Grundlage hierfür ist das Wiener Schweresystem mit dem durch v. Sterneck, v. Oppolzer und… …   Lexikon der gesamten Technik

  • Schwere Panzerjägerabteilung 653 — Aktiv März 1943–8. Mai 1945 (Kapitulation) Land Deutsches Reich …   Deutsch Wikipedia

  • Schwere 10-cm-Feldkanone 18 — Allgemeine Angaben …   Deutsch Wikipedia

  • Schwere Panzer Abteilung 504 — Période 13 janvier 1943 – mai 1945 Pays …   Wikipédia en Français

  • Schwere Stunde — ist eine novellistische Studie, die Thomas Mann zum Schillerjahr 1905 als Auftragsarbeit für den Simplicissimus geschrieben hat. Inhaltsverzeichnis 1 Inhalt 2 Anmerkungen 3 Ausgaben 4 …   Deutsch Wikipedia

  • Schwere-Ketten-Antikörper — sind Antikörper, die ausschließlich aus schweren Ketten bestehen. Sie unterscheiden sich strukturell von konventionellen IgG Antikörpern, die aus je zwei schweren und zwei leichten Ketten aufgebaut sind. Schwere Ketten Antikörper konnten in der… …   Deutsch Wikipedia

  • Schwere — (im weiteren Sinne Gravitation), ist die allen Körpern zukommende Eigenschaft, daß sich je zwei von ihnen gegenseitig anziehen mit einer Kraft, welche dem Producte ihrer Massen direct u. dem Quadrate ihrer Entfernung umgekehrt proportional ist,… …   Pierer's Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”