NP-Schwere

NP-schwer bzw. NP-hart (von englisch NP-hard, abgekürzt für Non-deterministic Polynomial-time hard) ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik. Er dient der Klassifizierung von Problemen, die im Sinne der formalen Theorie besonders aufwändig zu berechnen sind.

Sei L_1 \sub \Sigma^*, also eine formale Sprache.

L1 heißt nun NP-schwer, falls \forall L \in NP : L \le_P L_1, also alle L aus NP polynomial reduzierbar auf L1 sind.

Dies bedeutet, dass L1 ein Entscheidungsproblem ist und mindestens so schwer, wie jedes andere Problem aus NP. Diese intuitive Deutung wird gerechtfertigt duch die Tatsache, dass sich mit einem Algorithmus A, der L1 in Polynomialzeit löst, für jedes Problem aus NP ebenfalls ein polynomialer Algorithmus konstruieren ließe:

  1. führe zuerst die Reduktion auf L1 aus und
  2. anschließend Algorithmus A.

L1 selbst kann jedoch auch schwerer sein. Insbesondere muss L1 nicht notwendigerweise in NP liegen (liegt L1 jedoch zusätzlich in NP, so heißt L1 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überhinaus liegt das Halteproblem aber selbst nicht in NP, da es überhaupt nicht entscheidbar ist.

Siehe auch


Kategorie:Komplexitätstheorie

See also: NP-Schwere, Englische Sprache, Entscheidungsproblem, Erfüllbarkeitsproblem, Formale Sprache, Halteproblem, Informatik, Komplexitätstheorie, NP-Vollständigkeit, NP (Komplexitätsklasse)