NP-Härte

NP-Härte

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. Er gibt Aufschluss darüber, ob für alle Probleme aus der Komplexitätsklasse NP jeweils ein polynomieller Algorithmus existiert, der diese auf eine betrachtete formale Sprache reduziert.

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.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

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

  • Härte — ist der mechanische Widerstand, den ein Werkstoff der mechanischen Eindringung eines härteren Prüfkörpers entgegensetzt. Je nach der Art der Einwirkung unterscheidet man verschiedene Arten von Härte. So ist Härte nicht nur der Widerstand gegen… …   Deutsch Wikipedia

  • Härte — Härte. Im gewöhnlichen Sprachgebrauch wird teilweise jede Art der Aeußerung von Druckfestigkeit als Härte bezeichnet; der engere Begriff Härte aber bezeichnet die Druckfestigkeit eines Körpers nicht, soweit er als Ganzes, sondern nur, soweit er… …   Lexikon der gesamten Technik

  • Harte-Hanks — (nyse|HHS), headquartered in San Antonio, Texas, is a worldwide direct marketing company that provides a full range of marketing services. Consumers in California and Florida are probably most familiar with the company s PennySaver and The Flyer… …   Wikipedia

  • Härte — Härte, 1) die Eigenschaft eines Körpers, dass er seinen Zusammenhang auch bei einer stark von außen, durch Stoß od. Druck, einwirkenden Gewalt behauptet. Sie ist relativ, weil erfahrungsmäßig jeder Zusammenhang durch Stärke der mechanischen… …   Pierer's Universal-Lexikon

  • Harte — ist der Familienname folgender Personen: Bret Harte (1836–1902), amerikanischer Schriftsteller Friedrich Harte (1872–1941), deutscher Politiker (DVP) Ian Harte (* 1977), irischer Fußballspieler Harte ist die frühere Ortsbezeichnung von Hartau,… …   Deutsch Wikipedia

  • Harte — can refer to*Bret Harte (1836–1902), American author and poet *Bret Harte, California *Frank Harte, (1933 2005), traditional Irish singer *Ian Harte, Irish footballer …   Wikipedia

  • Härte (Begriffsklärung) — Härte steht für: Härte, eine Werkstoffeigenschaft Wasserhärte, die Äquivalentkonzentration der im Wasser gelösten Ionen der Erdalkalimetalle Härtegrad (Bleistift) bei Bleistiften eine unbillige Folge von Maßnahmen oder von Schicksalsschlägen,… …   Deutsch Wikipedia

  • Härte mit System – Wie Deutschland abschiebt — ist ein WDR Dokumentarfilm von Birand Bingül, Pagonis Pagonakis und Jutta Pinzler aus dem Jahre 2006 über die Abschiebe Praxis deutscher Behörden. Inhaltsverzeichnis 1 Inhalt 2 Reaktionen 3 Daten 4 Weblinks …   Deutsch Wikipedia

  • Harte Jungs (Begriffsklärung) — Harte Jungs ist Namensbestandteil von Harte Jungs, deutsche Filmkomödie (2000), siehe auch Knallharte Jungs Bad Boys – Harte Jungs, US amerikanischer Film von Michael Bay (1995) Greenfingers – Harte Jungs und zarte Triebe, britisch amerikanische… …   Deutsch Wikipedia

  • Harte [1] — Harte, Gebirgshöhe des Sächsischen Erzgebirges bei Zöblitz im Amte Lanterstein, mit großem Serpentinsteinlager …   Pierer's Universal-Lexikon

  • Harte [2] — Harte, Walter, geb. 1700 in England, war Geistlicher u. Begleiter Stanhopes, des natürlichen Sohnes des Lords Chesterfield; er st. 1744 in Bath u. schr.: Poems, 1727; Essais on satire. 1730; Essay on reason, 1735; History of Gustavus Adolphus,… …   Pierer's Universal-Lexikon

Share the article and excerpts

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