Notice: Unexpected clearActionName after getActionName already called in /var/www/html/includes/context/RequestContext.php on line 338
Satz von Ladner – Wikipedia (Deutsch) – Lokale Kopie Zum Inhalt springen

Satz von Ladner

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Ladner-Theorem)

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

Der Satz lautet damit formal: <math>\mathbf{P} \neq \mathbf{NP} \; \Rightarrow \; \mathbf{NPI} \neq \emptyset</math>.

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 <math>\mathbf{NPI}</math> liegen (falls <math>\mathbf{P}\ne\mathbf{NP}</math>). 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 <math>\mathbf{P}\ne\mathbf{NP}</math> gilt:<ref name="Odifreddi">Odifreddi 1999, S. 191</ref>

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

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

Beweisskizze

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

  • <math>R_{2e}:</math> Die Sprache <math>B</math> ist ungleich der Menge der Wörter, die <math>T_e</math> in Zeit kleiner <math>n^e</math> akzeptiert.
Formal: <math>B \neq \mathcal{L}(T_e)</math> mit Zeitschranke <math>n^e</math>
  • <math>R_{2e+1}:</math> Die Orakelmaschine <math>T_e</math> beschreibt keine Turingreduktion von <math>A</math> auf <math>B</math>, die in Zeit kleiner <math>n^e</math> berechnet werden kann.
Formal: <math>A \neq \mathcal{L}(T_e^B)</math> mit Zeitschranke <math>n^e</math>

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

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

<math>f(x)=\begin{cases} 

 x, & \text{wenn }g(\left| x \right|) \text{ gerade}\\
 a, & \text{sonst}

\end{cases}</math>

wobei <math>a\notin A</math> ein beliebiges Element ist.

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

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

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

Literatur

  • {{#invoke:Vorlage:Literatur|f}}
  • 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

Einzelnachweise

<references/>

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Satz_von_Ladner&oldid=1872369“