imported>Bithisarea: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-01-03T13:03:08Z

growthexperiments-addlink-summary-summary:3|0|0

Neue Seite

Der '''Satz von Ladner''' ist ein Satz aus der [[Theoretische Informatik|theoretischen Informatik]], der sich mit der Struktur der [[Komplexitätsklasse]] [[NP (Komplexitätsklasse)|NP]] in Bezug auf [[P (Komplexitätsklasse)|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 [[Formale Sprache|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ändig]]en 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 (Theoretische Informatik)|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 [[Erfüllbarkeitsproblem der Aussagenlogik|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 [[Turingmaschine]]n, 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-Turingmaschine]]n 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 [[Berechenbarkeit|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 ==
* {{Literatur|Autor = Sanjeev Arora und Boaz Barak|Titel=Computational Complexity. A Modern Approach|Verlag=Cambridge University Press |Ort=Cambridge|Jahr=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 ==
*Lance Fortnow: ''[http://oldblog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner's Theorem] (PDF-Datei; 72 kB)''

== Einzelnachweise ==
<references/>

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Satz (Mathematik)|Ladner]]

Satz von Ladner - Versionsgeschichte

imported>Bithisarea: /* growthexperiments-addlink-summary-summary:3|0|0 */