NP-Schwer

NP-Schwer

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:

  • Schwer — Schwêr, er, ste, adj. et adv. 1. Im eigentlichen physischen Verstande ist schwer, 1) absolute und ohne alle Rücksicht auf die Vergleichung oder Empfindung, was ein Bestreben hat, sich senkrecht nach einem gewissen Mittelpuncte zu bewegen. In… …   Grammatisch-kritisches Wörterbuch der Hochdeutschen Mundart

  • schwer — • schwer schwe|rer, schwers|te Kleinschreibung {{link}}K 89{{/link}}: – schwere (ernste, getragene) Musik – schweres (großkalibriges) Geschütz – schweres Wasser (Sauerstoff Deuterium Verbindung) – ein schwerer Junge (umgangssprachlich für… …   Die deutsche Rechtschreibung

  • schwer machen — schwer||ma|chen auch: schwer ma|chen 〈V. tr.; hat〉 jmdm. etwas schwer machen jmdm. bei etwas Schwierigkeiten machen, jmdm. etwas erschweren ● er macht ihr das Herz, Leben schwer; →a. schwer * * * schwer ma|chen, schwer|ma|chen <sw. V.; hat:… …   Universal-Lexikon

  • schwer verdaulich — schwer|ver|dau|lich auch: schwer ver|dau|lich 〈Adj.〉 schwer zu verdauen; Sy schwerverträglich ● schwer verdauliche Speisen * * * schwer ver|dau|lich, schwer|ver|dau|lich <Adj.>: (von Speisen) schwer zu verdauend, sich nur schwer verdauen… …   Universal-Lexikon

  • schwer — Adj. (Grundstufe) von großem Gewicht, nicht leicht Beispiele: Das Gepäck ist sehr schwer. Sie ist 50 Kilo schwer. schwer Adj. (Aufbaustufe) mit großer körperlicher Anstrengung oder vielen Schwierigkeiten verbunden Synonyme: hart, mühevoll, mühsam …   Extremes Deutsch

  • schwer beladen — schwer|be|la|den auch: schwer be|la|den 〈Adj.〉 mit großer Last, schweren Dingen versehen ● ein schwer beladener Möbeltransporter; 〈aber〉 der Möbeltransporter war schwerbeladen / schwer beladen * * * schwer be|la|den, schwer|be|la|den <Adj.> …   Universal-Lexikon

  • schwer löslich — schwer|lös|lich auch: schwer lös|lich 〈Adj.〉 nur langsam löslich ● eine schwer lösliche Substanz * * * schwer lös|lich, schwer|lös|lich <Adj.>: nur schwer löslich: eine schwer lösliche Substanz. * * * schwer lös|lich: s. ↑schwer (2 b) …   Universal-Lexikon

  • schwer bewaffnet — schwer|be|waff|net auch: schwer be|waff|net 〈Adj.〉 viele Waffen tragend ● ein schwer bewaffneter Soldat * * * schwer be|waff|net, schwer|be|waff|net <Adj.>: mit [mehreren] großkalibrigen Waffen ausgerüstet: ein schwer bewaffneter Polizist.… …   Universal-Lexikon

  • schwer krank — schwer|krank auch: schwer krank 〈Adj.〉 1. sehr, ernstlich krank 2. 〈Jägerspr.〉 angeschossen ● ein schwer kranker Patient * * * schwer krank, schwer|krank <Adj.>: von schwerer Krankheit betroffen; ernstlich krank: ein schwer kranker Patient …   Universal-Lexikon

  • schwer verletzt — schwer|ver|letzt auch: schwer ver|letzt 〈Adj.〉 eine schwere Verletzung habend ● er wurde bei dem Unfall schwer verletzt * * * schwer ver|letzt, schwer|ver|letzt <Adj.>: gefährlich verletzt: schwer verletzte Opfer. * * * schwer ver|letzt: s …   Universal-Lexikon

  • schwer verträglich — schwer|ver|träg|lich auch: schwer ver|träg|lich 〈Adj.〉 = schwerverdaulich * * * schwer ver|träg|lich, schwer|ver|träg|lich <Adj.>: (von Speisen o. Ä.) sich nur schwer vertragen lassend: schwer verträgliche Speisen, Medikamente. * * * schwer …   Universal-Lexikon

Share the article and excerpts

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