Satz von Ladner

Kernaussage und Einordnung

Der Satz von Ladner ist ein Ergebnis der theoretischen Informatik über die Struktur der Komplexitätsklasse NP im Verhältnis zu P. Richard Ladner bewies ihn 1975. Er beantwortet eine wichtige Zwischenfrage des P-NP-Problems: Gibt es Probleme, die zwar in NP liegen, aber weder in Polynomialzeit lösbar noch NP-vollständig sind?

P ist die Klasse der Sprachen, die von einer deterministischen Turingmaschine in Polynomialzeit entschieden werden können. NP umfasst P. Die NP-vollständigen Probleme gelten als die schwierigsten Probleme innerhalb von NP. Ob P eine echte Teilmenge von NP ist, ist weiterhin offen.

Der Satz von Ladner besagt: Falls P ≠ NP gilt, existieren Probleme in NP, die weder in P liegen noch NP-vollständig sind. Die Klasse dieser Probleme heißt NP-intermediate oder NPI. Formal lautet die Aussage:

P ≠ NP ⇒ NPI ≠ ∅.

Damit zeigt der Satz, dass zwischen den leicht lösbaren Problemen in P und den NP-vollständigen Problemen eine weitere Klasse liegen muss, sofern P und NP verschieden sind.

Bedeutung und Verallgemeinerung

Für den ursprünglichen Beweis konstruierte Ladner ein künstliches Problem. Dieses Problem besitzt keinerlei praktische Relevanz. Bis heute ist nicht bekannt, ob auch natürliche Probleme in NPI liegen, falls P ≠ NP gilt. Es wird jedoch vermutet, dass beispielsweise die Primfaktorzerlegung zu dieser Klasse gehören könnte.

Der Satz lässt sich verallgemeinern und gilt dann unabhängig von der Annahme P ≠ NP: Unter Polynomialzeit-Reduktionen gibt es keine minimale Komplexitätsklasse über P. Gemeint sind sowohl Turingreduktionen als auch many-one-Reduktionen.

Das bedeutet: Ist ein Problem A echt schwieriger als alle Probleme in P, dann gibt es ein Problem B, das ebenfalls nicht in P liegt, aber echt leichter als A ist. Eine Klasse oberhalb von P kann daher nicht das unmittelbar nächstschwierigere Niveau bilden; zwischen P und jedem echt schwierigeren Problem existieren weitere Schwierigkeitsstufen.

Ausgangslage der Beweisskizze

Man betrachtet zunächst eine entscheidbare Sprache A, die nicht in P liegt. Unter der Voraussetzung P ≠ NP kann A als SAT gewählt werden. Konstruiert wird eine Sprache B mit folgenden Eigenschaften:

• B liegt nicht in P.
• B ist unter einer many-one-Reduktion in Polynomialzeit auf A reduzierbar: B ≤ₚ A.
• A ist nicht unter einer Turingreduktion in Polynomialzeit auf B reduzierbar: A ≰ₚ B.

Damit ist B höchstens so schwierig wie A, aber nicht in P. Zugleich verhindert die letzte Eigenschaft, dass A auf B reduziert werden kann. Für geeignete Ausgangssprache A erhält man so ein Problem, das zwischen P und der Schwierigkeit von A liegt.

Dazu werden alle Turingmaschinen T₁, T₂, … aufgelistet. Die e-te Maschine hält auf Eingabe x spätestens nach |x|ᵉ Schritten; außerdem zählt jede Maschine ihre Schritte. Ebenso werden zeitbeschränkte Orakel-Turingmaschinen T₁ᴮ, T₂ᴮ, … betrachtet, die auf das Orakel B zugreifen können.

Für jede Maschine werden zwei Anforderungen formuliert:

• R₂ₑ: B ist nicht gleich der von Tₑ in Zeit kleiner als nᵉ akzeptierten Sprache. Formal: B ≠ L(Tₑ) mit Zeitschranke nᵉ.
• R₂ₑ₊₁: Tₑᴮ beschreibt keine Turingreduktion von A auf B, die in Zeit kleiner als nᵉ arbeitet. Formal: A ≠ L(Tₑᴮ) mit Zeitschranke nᵉ.

Da jede Turingmaschine durch das Hinzufügen redundanter Zustände unendlich oft in der Aufzählung vorkommt, folgt aus der Erfüllung aller Anforderungen R₂ₑ, dass B nicht in P liegt. Aus der Erfüllung aller Anforderungen R₂ₑ₊₁ folgt entsprechend, dass es keine Polynomialzeit-Turingreduktion von A auf B gibt.

Konstruktion der Sprache B

Die Sprache B wird aus A erzeugt, indem hinreichend große Abschnitte von A entfernt werden. Eine polynomiell berechenbare Funktion g legt fest, welche Anforderung in einem bestimmten Konstruktionsschritt bearbeitet wird. Es gilt:

B = {x ∈ A | g(|x|) ist gerade}.

Für gerade Werte von g werden Wörter aus A in B übernommen; für ungerade Werte werden sie ausgelassen. Dadurch ist B über die Funktion f many-one in Polynomialzeit auf A reduzierbar:

f(x) = x, wenn g(|x|) gerade ist,

f(x) = a, sonst,

wobei a ∉ A ein beliebiges Element ist.

Die Funktion g beginnt mit g(0) = 0. Für s > 0 werden die Werte g(0), g(1), …, g(s−1) nacheinander berechnet. Die Berechnung wird nach s Schritten beendet. Sei n die größte Zahl, für die g(n) innerhalb dieser s Schritte bestimmt werden kann.

Ist g(n) = 2e, wird nach einem Wort z gesucht, für das B(z) ≠ Tₑ(z) gilt. Es werden höchstens s Suchschritte ausgeführt, damit g polynomiell in s berechenbar bleibt. Wird ein solches z gefunden, ist R₂ₑ erfüllt und g(s) = g(n) + 1 = 2e + 1. Wird kein z gefunden, bleibt offen, ob die Anforderung bereits erfüllt ist; deshalb setzt man g(s) = g(n) und sucht weiter.

Ist g(n) = 2e + 1, wird analog nach einem Wort z gesucht, für das A(z) ≠ Tₑᴮ(z) gilt. Findet man ein solches Wort, ist R₂ₑ₊₁ erfüllt und g(s) = g(n) + 1 = 2(e + 1). Andernfalls wird die gleiche Anforderung weiterverfolgt.

Zum Abschluss muss gezeigt werden, dass alle Anforderungen erfüllt werden. Dafür genügt es, die Surjektivität von g zu zeigen, also dass jeder benötigte Wert von g irgendwann angenommen wird. Angenommen, es gäbe ein n, sodass g(n) = g(m) für alle m > n. Falls dieser dauerhafte Wert eine gerade Anforderung R₂ₑ wäre, wäre B polynomiell entscheidbar, obwohl B sich nur auf endlich vielen Wörtern von der nicht in P liegenden Sprache A unterscheidet. Das wäre ein Widerspruch. Falls der dauerhafte Wert eine ungerade Anforderung R₂ₑ₊₁ wäre, wäre B endlich. Da A nicht in P liegt, kann A jedoch nicht auf eine endliche Sprache reduziert werden. Auch das ist ein Widerspruch. Somit kann g nicht dauerhaft bei einer Anforderung stehen bleiben; alle Anforderungen werden erfüllt.