NP-Schwere

Kernidee und Einordnung

NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie alle Probleme der Komplexitätsklasse NP. Die Komplexitätstheorie untersucht, wie schwierig Probleme algorithmisch zu lösen sind.

NP ist die Klasse der Probleme, die mit einer nichtdeterministischen Turingmaschine in Polynomialzeit gelöst werden können. Anschaulich handelt es sich um Entscheidungsprobleme, bei denen sich eine gegebene, beispielsweise geratene Lösung effizient überprüfen lässt.

Ein Problem ist NP-schwer, wenn jedes Problem aus NP in Polynomialzeit auf dieses Problem reduziert werden kann. Gäbe es also einen deterministischen Polynomialzeit-Algorithmus für ein NP-schweres Problem, könnte man damit auch jedes beliebige Problem aus NP in Polynomialzeit lösen. Ein NP-schweres Problem muss selbst nicht in NP liegen. Liegt es zusätzlich in NP, wird es NP-vollständig genannt.

Problemreduktionen als Vergleichsmethode

Um die Schwierigkeit zweier Probleme zu vergleichen, verwendet man Problemreduktionen. Ein Problem A heißt auf ein Problem B reduzierbar, wenn jeder Algorithmus, der B löst, auch zur Lösung von A verwendet werden kann. Dazu wird eine Instanz von A in eine Instanz von B umgerechnet und anschließend B gelöst.

Für Aussagen über die Effizienz ist entscheidend, wie aufwendig diese Umrechnung ist. Wird die Zahl der Rechenschritte einer Reduktion in Abhängigkeit von der Eingabelänge durch ein Polynom beschrieben und nicht etwa durch eine Exponentialfunktion, handelt es sich um eine Polynomialzeitreduktion.

Kann Problem 1 durch eine Polynomialzeitreduktion in Problem 2 überführt werden und kann Problem 2 ebenfalls mit polynomialem Aufwand gelöst werden, dann kann auch Problem 1 in Polynomialzeit gelöst werden. Genau deshalb zeigt die Reduzierbarkeit aller NP-Probleme auf ein Problem dessen besondere Schwierigkeit.

Formale Definition und NP-Vollständigkeit

Sei L' ⊆ Σ* eine formale Sprache. L' heißt NP-schwer, wenn gilt:

∀ L ∈ NP: L ≼ₚ L'

Das bedeutet: Alle Sprachen beziehungsweise Probleme L aus NP sind polynomiell auf L' reduzierbar. Die Definition wird dadurch begründet, dass sich für jedes Problem aus NP ein Polynomialzeit-Algorithmus konstruieren ließe, sobald ein Algorithmus A existiert, der L' in Polynomialzeit löst:

• Zuerst wird die Instanz des Problems auf L' reduziert.
• Anschließend wird Algorithmus A auf die erzeugte Instanz angewendet.

L' kann allerdings auch schwieriger sein als die Probleme in NP und muss nicht selbst zu NP gehören. Falls L' zusätzlich in NP liegt, ist L' NP-vollständig.

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. Nach dem Satz von Cook ist SAT damit ein schwerstes Problem in NP.

SAT ist nicht das einzige Problem dieser Art. Richard M. Karp zeigte, dass es in NP Probleme gibt, auf die SAT reduziert werden kann. Solche Probleme sind genauso schwer wie SAT. Die schwersten Probleme innerhalb von NP werden NP-vollständig genannt. Alle Probleme, auch solche außerhalb von NP, auf die SAT in Polynomialzeit reduziert werden kann, heißen NP-schwer. In Darstellungen der Beziehungen zwischen P, NP, NP-schweren und NP-vollständigen Problemen werden die leere Sprache und ihr Komplement häufig außen vor gelassen, obwohl beide in P und NP liegen, aber nicht NP-schwer sind.

Beispiel: das Halteproblem

Ein klassisches NP-schweres Problem, das nicht in NP liegt, ist das Halteproblem für Turingmaschinen.

Das Erfüllbarkeitsproblem SAT kann auf das Halteproblem reduziert werden. Dazu wird eine SAT-Instanz in eine Turingmaschine umgewandelt. Diese Turingmaschine probiert nacheinander alle möglichen Belegungen durch und hält, sobald sie eine erfüllende Belegung gefunden hat. Gibt es keine erfüllende Belegung, läuft sie stattdessen in einer Endlosschleife weiter.

Das Halteproblem liegt nicht in NP, weil es überhaupt nicht entscheidbar ist. Dieses Beispiel zeigt, dass NP-Schwere nicht voraussetzt, dass ein Problem selbst in NP liegt: Ein NP-schweres Problem kann auch außerhalb von NP liegen und sogar unentscheidbar sein.