Satz von Ladner

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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.

  • 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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b Odifreddi 1999, S. 191