Satz von Ladner

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

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

Der Satz lautet damit formal: \mathcal{P} \neq \mathcal{NP} \Rightarrow \mathcal{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 NPI liegen (falls P ≠ NP). Es wird jedoch vermutet, dass dies z.B. für die Primfaktorzerlegung gilt.

Der Satz lässt sich wie folgt generalisieren, sodass er unabhängig von der Annahme P ≠ NP gilt:[1]

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

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

Beweisskizze[Bearbeiten]

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 A \notin P gegeben. Unter der Voraussetzung P \neq NP kann man A = SAT wählen. Man definiert eine Sprache B \notin P, die auf A polynomzeit-reduzierbar ist, aber nicht in P liegt: B \leq_p A (unter many-one-Reduktion) und A \not\le_p B (unter Turing-Reduktion). Sei T_1, T_2, \dotsb 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, \dotsb 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 \neq L(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 \neq L(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, \dotsb unendlich oft vorkommt, ist B \notin P, 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(x) 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{cases}
  x,  & \text{wenn }g(\left| x \right|) \text{ gerade}\\
  a, & \text{sonst}
\end{cases}

wobei a ein beliebiges Element \notin A ist.

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

  • g(n) = 2e: Man sucht ein Wort z mit B(z) \neq 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) \neq 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 P unterscheidet. Ist g(n) = R_{2e+1}, wäre B endlich. Da A aber nicht in P liegt, lässt es sich nicht auf eine endliche Sprache reduzieren.

Literatur[Bearbeiten]

  •  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

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. a b Odifreddi 1999, S. 191