Satz von Ladner

Der Satz von Ladner ist ein Satz aus der theoretischen Informatik, der sich mit der Struktur der Komplexitätsklasse NP in Bezug auf P befasst. Er wurde 1975 von Richard Ladner bewiesen.

Die Klasse $𝐍𝐏$ umfasst die Komplexitätsklasse $𝐏$ der in Polynomzeit deterministisch entscheidbaren Sprachen. Die Frage, ob $𝐏$ eine echte Teilmenge von $𝐍𝐏$ ist, ist nach wie vor offen (siehe P-NP-Problem). Die NP-vollständigen Probleme sind die schwierigsten Probleme in $𝐍𝐏$. Die Frage, ob Probleme in $𝐍𝐏$ existieren, die weder $𝐍𝐏$-vollständig sind, noch in $𝐏$ liegen, wird vom Satz von Ladner positiv beantwortet, falls $𝐏\ne 𝐍𝐏$ gilt. Die Menge dieser Probleme wird NP-intermediate oder $𝐍𝐏𝐈$ genannt.

Der Satz lautet damit formal: $𝐏\ne 𝐍𝐏\Rightarrow 𝐍𝐏𝐈\ne \mathrm{\varnothing }$.

Für den Beweis des Satzes wurde von Ladner ein künstliches Problem generiert, welches keinerlei praktische Relevanz besitzt. Es ist nicht bekannt, ob auch natürliche Probleme in $𝐍𝐏𝐈$ liegen (falls $𝐏\ne 𝐍𝐏$). Es wird jedoch vermutet, dass das z. B. für die Primfaktorzerlegung gilt.

Der Satz lässt sich verallgemeinern, sodass er unabhängig von der Annahme $𝐏\ne 𝐍𝐏$ gilt:

Unter Polynomialzeit-Reduktion (sowohl Turingreduktion als auch many-one-Reduktion) gibt es keine minimale Klasse über $𝐏$.

Das heißt, wenn ein Problem $A$ echt schwerer als die Probleme in $𝐏$ ist, dann gibt es Probleme $B$, die ebenfalls nicht in $𝐏$ liegen, aber echt leichter als $A$ sind.

Beweisskizze

Dieser Beweis, der auch die erste angegebene Verallgemeinerung abdeckt, folgt im Wesentlichen Odifreddi 1999 und basiert auf Ladners ursprünglichem Beweis. Ein alternativer Beweis, in dem SAT gepaddet wird, wird von Arora und Barak 2009 beschrieben.

Sei eine entscheidbare Sprache $A\notin 𝐏$ gegeben. Unter der Voraussetzung $𝐏\ne 𝐍𝐏$ kann man $A=\mathrm{S}\mathrm{A}\mathrm{T}$ wählen. Man definiert eine Sprache $B\notin 𝐏$, die auf $A$ polynomzeit-reduzierbar ist, aber nicht in $𝐏$ liegt: $B{\le }_{\mathrm{P}}A$ (unter many-one-Reduktion) und $A{\le }_{\mathrm{P}}B$ (unter Turing-Reduktion). Sei $T_1,T_2,\dots$ eine Aufzählung aller Turingmaschinen, wobei jede zusätzlich die Zahl der Schritte mitzählt und die $e$-te Maschine auf Eingabe $x$ spätestens nach Zeit ${\left|x\right|}^e$ hält. Sei $T_1^B,T_2^B,\dots$ eine Auflistung der auf die gleiche Weise zeitbeschränkten Orakel-Turingmaschinen mit Orakel $B$. Dann gibt es für alle Maschinen $T_e,T_e^B$ zwei Anforderungen, die $B$ erfüllen muss:

• $R_{2e}:$ Die Sprache $B$ ist ungleich der Menge der Wörter, die $T_e$ in Zeit kleiner $n^e$ akzeptiert.

Formal: $B\ne ℒ(T_e)$ mit Zeitschranke $n^e$

• $R_{2e+1}:$ Die Orakelmaschine $T_e$ beschreibt keine Turingreduktion von $A$ auf $B$, die in Zeit kleiner $n^e$ berechnet werden kann.

Formal: $A\ne ℒ(T_e^B)$ mit Zeitschranke $n^e$

Da jede Turingmaschine (etwa durch Hinzufügen redundanter Zustände) in der Aufzählung $T_1,T_2,\dots$ unendlich oft vorkommt, ist $B\notin 𝐏$, wenn es alle $R_{2e}$ erfüllt. Analog gibt es, wenn alle $R_{2e+1}$ gelten, keine Polynomzeitreduktion von $A$ auf $B$.

$B$ entsteht nun aus $A$, indem hinreichend große Abschnitte aus $A$ entfernt werden, sodass $A$ nicht polynomiell auf $B$ reduziert werden kann, $B$ aber trotzdem noch nicht in P liegt. Zur Konstruktion wird eine polynomiell berechenbare Funktion $g$ definiert, die zu jedem Schritt $x$ der Konstruktion angibt, welche Anforderung gerade verfolgt wird. Dann liegen genau die Elemente $x$ in $B$, sodass in Schritt $\left|x\right|$ eine Anforderung der Form $2e$ verfolgt wurde: $B=\{x\in A|g(\left|x\right|)\text{ gerade}\}$. Somit lässt sich $B$ über folgende Funktion $f$ polynomiell auf $A$ many-one reduzieren:

$f(x)=\{\begin{array}{cc}x,& \text{wenn }g(\left|x\right|)\text{ gerade}\\ a,& \text{sonst}\end{array}$

wobei $a\notin A$ ein beliebiges Element ist.

Als erste Anforderung wird $g(0)=0$ gewählt. Für $s>0$ wird $g(s)$ induktiv so definiert, dass es in Polynomzeit berechnet werden kann. Man beginnt, nacheinander die Werte $g(0),g(1),\dots ,g(s-1)$ zu berechnen und bricht nach $s$ Berechnungsschritten ab. $n$ sei die größte Zahl, sodass $g(n)$ in $s$ Schritten bestimmen werden kann. Dann gibt es zwei Fälle:

• $g(n)=2e$: Man sucht ein Wort $z$ mit $B(z)\ne T_e(z)$. Da $g$ polynomiell in $s$ berechenbar sein soll, werden nur die ersten $s$ Berechnungsschritte der Suche ausgeführt.
  • Wird dabei ein $z$ gefunden, ist $R_{2e}$ erfüllt. Dann ist $g(s)=g(n)+1=2e+1$.
  • Sonst ist nicht bekannt, ob $R_{2e}$ schon erfüllt wurde und $g(s)=g(n)$, um weiterhin zu versuchen, $R_{2e}$ zu erfüllen.
• $g(n)=2e+1$: Man sucht ein Wort $z$ mit $A(z)\ne T_e^B(z)$. Analog zu $2e$ werden nur $s$ Schritte durchgeführt.
  • Findet man ein $z$, ist $R_{2e+1}$ erfüllt und $g(s)=g(n)+1=2(e+1)$.
  • Sonst ist nicht bekannt, ob $R_{2e+1}$ schon erfüllt wurde und $g(s)=g(n)$, um weiterhin zu versuchen, $R_{2e+1}$ zu erfüllen.

Zu zeigen ist nun, dass alle Anforderungen erfüllt werden. Dazu genügt es, zu zeigen, dass $g$ surjektiv ist. Angenommen, es gibt ein $n$ mit $g(n)=g(m)$ für alle $m>n$. Ist $g(n)=R_{2e}$, wäre $B$ polynomiell entscheidbar, obwohl es sich nur auf endlich vielen Wörtern von $A\notin 𝐏$ unterscheidet. Ist $g(n)=R_{2e+1}$, wäre $B$ endlich. Da $A$ aber nicht in $𝐏$ liegt, lässt es sich nicht auf eine endliche Sprache reduzieren.

Literatur

• Vorlage:Literatur
• Ladner, Richard: On the Structure of Polynomial Time Reducibility. Journal of the ACM (JACM) 22 (1): 155–171, 1975.
• Piergiorgio Odifreddi: Classical Recursion Theory, Volume II. Elsevier, 1999. ISBN 0-444-50205-X

Weblinks

• Lance Fortnow: Two Proofs of Ladner's Theorem (PDF-Datei; 72 kB)