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 ${\displaystyle \mathbf {NP} }$ umfasst die Komplexitätsklasse ${\displaystyle \mathbf {P} }$ der in Polynomzeit deterministisch entscheidbaren Sprachen. Die Frage, ob ${\displaystyle \mathbf {P} }$ eine echte Teilmenge von ${\displaystyle \mathbf {NP} }$ ist, ist nach wie vor offen (siehe P-NP-Problem). Die NP-vollständigen Probleme sind die schwierigsten Probleme in ${\displaystyle \mathbf {NP} }$. Die Frage, ob Probleme in ${\displaystyle \mathbf {NP} }$ existieren, die weder ${\displaystyle \mathbf {NP} }$-vollständig sind, noch in ${\displaystyle \mathbf {P} }$ liegen, wird vom Satz von Ladner positiv beantwortet, falls ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$ gilt. Die Menge dieser Probleme wird NP-intermediate oder ${\displaystyle \mathbf {NPI} }$ genannt.

Der Satz lautet damit formal: ${\displaystyle \mathbf {P} \neq \mathbf {NP} \;\Rightarrow \;\mathbf {NPI} \neq \emptyset }$.

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 ${\displaystyle \mathbf {NPI} }$ liegen (falls ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$). 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 ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$ gilt:^[1]

Unter Polynomialzeit-Reduktion (sowohl Turingreduktion als auch many-one-Reduktion) gibt es keine minimale Klasse über ${\displaystyle \mathbf {P} }$.

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

Dieser Beweis, der auch die erste angegebene Verallgemeinerung abdeckt, folgt im Wesentlichen Odifreddi 1999^[1] 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 ${\displaystyle A\notin \mathbf {P} }$ gegeben. Unter der Voraussetzung ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$ kann man ${\displaystyle A=\mathrm {SAT} }$ wählen. Man definiert eine Sprache ${\displaystyle B\notin \mathbf {P} }$, die auf ${\displaystyle A}$ polynomzeit-reduzierbar ist, aber nicht in ${\displaystyle \mathbf {P} }$ liegt: ${\displaystyle B\leq _{\mathrm {P} }A}$ (unter many-one-Reduktion) und ${\displaystyle A\not \leq _{\mathrm {P} }B}$ (unter Turing-Reduktion). Sei ${\displaystyle T_{1},T_{2},\dotsc }$ eine Aufzählung aller Turingmaschinen, wobei jede zusätzlich die Zahl der Schritte mitzählt und die ${\displaystyle e}$-te Maschine auf Eingabe ${\displaystyle x}$ spätestens nach Zeit ${\displaystyle \left|x\right|^{e}}$ hält. Sei ${\displaystyle T_{1}^{B},T_{2}^{B},\dotsc }$ eine Auflistung der auf die gleiche Weise zeitbeschränkten Orakel-Turingmaschinen mit Orakel ${\displaystyle B}$. Dann gibt es für alle Maschinen ${\displaystyle T_{e},T_{e}^{B}}$ zwei Anforderungen, die ${\displaystyle B}$ erfüllen muss:

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

Formal: ${\displaystyle B\neq {\mathcal {L}}(T_{e})}$ mit Zeitschranke ${\displaystyle n^{e}}$

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

Formal: ${\displaystyle A\neq {\mathcal {L}}(T_{e}^{B})}$ mit Zeitschranke ${\displaystyle n^{e}}$

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

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

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

wobei ${\displaystyle a\notin A}$ ein beliebiges Element ist.

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

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

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

• Sanjeev Arora und Boaz Barak: Computational Complexity. A Modern Approach. Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4. 
• 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

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

1. ↑ ^{a b} Odifreddi 1999, S. 191