Satz von Ladner

Satz aus der theoretischen Informatik
(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 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 gilt. Die Menge dieser Probleme wird NP-intermediate oder genannt.

Der Satz lautet damit formal: .

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 ). 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 gilt:[1]

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

Das heißt, wenn ein Problem echt schwerer als die Probleme in ist, dann gibt es Probleme , die ebenfalls nicht in liegen, aber echt leichter als 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   gegeben. Unter der Voraussetzung   kann man   wählen. Man definiert eine Sprache  , die auf   polynomzeit-reduzierbar ist, aber nicht in   liegt:   (unter many-one-Reduktion) und   (unter Turing-Reduktion). Sei   eine Aufzählung aller Turingmaschinen, wobei jede zusätzlich die Zahl der Schritte mitzählt und die  -te Maschine auf Eingabe   spätestens nach Zeit   hält. Sei   eine Auflistung der auf die gleiche Weise zeitbeschränkten Orakel-Turingmaschinen mit Orakel  . Dann gibt es für alle Maschinen   zwei Anforderungen, die   erfüllen muss:

  •   Die Sprache   ist ungleich der Menge der Wörter, die   in Zeit kleiner   akzeptiert.
Formal:   mit Zeitschranke  
  •   Die Orakelmaschine   beschreibt keine Turingreduktion von   auf  , die in Zeit kleiner   berechnet werden kann.
Formal:   mit Zeitschranke  

Da jede Turingmaschine (etwa durch Hinzufügen redundanter Zustände) in der Aufzählung   unendlich oft vorkommt, ist  , wenn es alle   erfüllt. Analog gibt es, wenn alle   gelten, keine Polynomzeitreduktion von   auf  .

  entsteht nun aus  , indem hinreichend große Abschnitte aus   entfernt werden, sodass   nicht polynomiell auf   reduziert werden kann,   aber trotzdem noch nicht in P liegt. Zur Konstruktion wird eine polynomiell berechenbare Funktion   definiert, die zu jedem Schritt   der Konstruktion angibt, welche Anforderung gerade verfolgt wird. Dann liegen genau die Elemente   in  , sodass in Schritt   eine Anforderung der Form   verfolgt wurde:  . Somit lässt sich   über folgende Funktion   polynomiell auf   many-one reduzieren:

 

wobei   ein beliebiges Element ist.

Als erste Anforderung wird   gewählt. Für   wird   induktiv so definiert, dass es in Polynomzeit berechnet werden kann. Man beginnt, nacheinander die Werte   zu berechnen und bricht nach   Berechnungsschritten ab.   sei die größte Zahl, sodass   in   Schritten bestimmen werden kann. Dann gibt es zwei Fälle:

  •  : Man sucht ein Wort   mit  . Da   polynomiell in   berechenbar sein soll, werden nur die ersten   Berechnungsschritte der Suche ausgeführt.
    • Wird dabei ein   gefunden, ist   erfüllt. Dann ist  .
    • Sonst ist nicht bekannt, ob   schon erfüllt wurde und  , um weiterhin zu versuchen,   zu erfüllen.
  •  : Man sucht ein Wort   mit  . Analog zu   werden nur   Schritte durchgeführt.
    • Findet man ein  , ist   erfüllt und  .
    • Sonst ist nicht bekannt, ob   schon erfüllt wurde und  , um weiterhin zu versuchen,   zu erfüllen.

Zu zeigen ist nun, dass alle Anforderungen erfüllt werden. Dazu genügt es, zu zeigen, dass   surjektiv ist. Angenommen, es gibt ein   mit   für alle  . Ist  , wäre   polynomiell entscheidbar, obwohl es sich nur auf endlich vielen Wörtern von   unterscheidet. Ist  , wäre   endlich. Da   aber nicht in   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
Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b Odifreddi 1999, S. 191