www.wikidata.de-de.nina.az

Satz von Ladner Der ist ein Satz aus der theoretischen Informatik der sich mit der Struktur der Komplexitätsklasse NP in

Satz von Ladner

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:

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 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.
  • Die Orakelmaschine beschreibt keine Turingreduktion von auf , die in Zeit kleiner berechnet werden kann.

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

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. ↑ Odifreddi 1999, S. 191
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Satz von Ladner ist ein Satz aus der theoretischen Informatik der sich mit der Struktur der Komplexitatsklasse NP in Bezug auf P befasst Er wurde 1975 von Richard Ladner bewiesen Die Klasse N P displaystyle mathbf NP umfasst die Komplexitatsklasse P displaystyle mathbf P der in Polynomzeit deterministisch entscheidbaren Sprachen Die Frage ob P displaystyle mathbf P eine echte Teilmenge von N P displaystyle mathbf NP ist ist nach wie vor offen siehe P NP Problem Die NP vollstandigen Probleme sind die schwierigsten Probleme in N P displaystyle mathbf NP Die Frage ob Probleme in N P displaystyle mathbf NP existieren die weder N P displaystyle mathbf NP vollstandig sind noch in P displaystyle mathbf P liegen wird vom Satz von Ladner positiv beantwortet falls P N P displaystyle mathbf P neq mathbf NP gilt Die Menge dieser Probleme wird NP intermediate oder N P I displaystyle mathbf NPI genannt Der Satz lautet damit formal P N P N P I displaystyle mathbf P neq mathbf NP Rightarrow mathbf NPI neq emptyset Fur den Beweis des Satzes wurde von Ladner ein kunstliches Problem generiert welches keinerlei praktische Relevanz besitzt Es ist nicht bekannt ob auch naturliche Probleme in N P I displaystyle mathbf NPI liegen falls P N P displaystyle mathbf P neq mathbf NP Es wird jedoch vermutet dass das z B fur die Primfaktorzerlegung gilt Der Satz lasst sich verallgemeinern sodass er unabhangig von der Annahme P N P displaystyle mathbf P neq mathbf NP gilt 1 Unter Polynomialzeit Reduktion sowohl Turingreduktion als auch many one Reduktion gibt es keine minimale Klasse uber P displaystyle mathbf P Das heisst wenn ein Problem A displaystyle A echt schwerer als die Probleme in P displaystyle mathbf P ist dann gibt es Probleme B displaystyle B die ebenfalls nicht in P displaystyle mathbf P liegen aber echt leichter als A displaystyle A sind Inhaltsverzeichnis 1 Beweisskizze 2 Literatur 3 Weblinks 4 EinzelnachweiseBeweisskizze BearbeitenDieser Beweis der auch die erste angegebene Verallgemeinerung abdeckt folgt im Wesentlichen Odifreddi 1999 1 und basiert auf Ladners ursprunglichem Beweis Ein alternativer Beweis in dem SAT gepaddet wird wird von Arora und Barak 2009 beschrieben Sei eine entscheidbare Sprache A P displaystyle A notin mathbf P nbsp gegeben Unter der Voraussetzung P N P displaystyle mathbf P neq mathbf NP nbsp kann man A S A T displaystyle A mathrm SAT nbsp wahlen Man definiert eine Sprache B P displaystyle B notin mathbf P nbsp die auf A displaystyle A nbsp polynomzeit reduzierbar ist aber nicht in P displaystyle mathbf P nbsp liegt B P A displaystyle B leq mathrm P A nbsp unter many one Reduktion und A P B displaystyle A not leq mathrm P B nbsp unter Turing Reduktion Sei T 1 T 2 displaystyle T 1 T 2 dotsc nbsp eine Aufzahlung aller Turingmaschinen wobei jede zusatzlich die Zahl der Schritte mitzahlt und die e displaystyle e nbsp te Maschine auf Eingabe x displaystyle x nbsp spatestens nach Zeit x e displaystyle left x right e nbsp halt Sei T 1 B T 2 B displaystyle T 1 B T 2 B dotsc nbsp eine Auflistung der auf die gleiche Weise zeitbeschrankten Orakel Turingmaschinen mit Orakel B displaystyle B nbsp Dann gibt es fur alle Maschinen T e T e B displaystyle T e T e B nbsp zwei Anforderungen die B displaystyle B nbsp erfullen muss R 2 e displaystyle R 2e nbsp Die Sprache B displaystyle B nbsp ist ungleich der Menge der Worter die T e displaystyle T e nbsp in Zeit kleiner n e displaystyle n e nbsp akzeptiert Formal B L T e displaystyle B neq mathcal L T e nbsp mit Zeitschranke n e displaystyle n e nbsp R 2 e 1 displaystyle R 2e 1 nbsp Die Orakelmaschine T e displaystyle T e nbsp beschreibt keine Turingreduktion von A displaystyle A nbsp auf B displaystyle B nbsp die in Zeit kleiner n e displaystyle n e nbsp berechnet werden kann Formal A L T e B displaystyle A neq mathcal L T e B nbsp mit Zeitschranke n e displaystyle n e nbsp Da jede Turingmaschine etwa durch Hinzufugen redundanter Zustande in der Aufzahlung T 1 T 2 displaystyle T 1 T 2 dotsc nbsp unendlich oft vorkommt ist B P displaystyle B notin mathbf P nbsp wenn es alle R 2 e displaystyle R 2e nbsp erfullt Analog gibt es wenn alle R 2 e 1 displaystyle R 2e 1 nbsp gelten keine Polynomzeitreduktion von A displaystyle A nbsp auf B displaystyle B nbsp B displaystyle B nbsp entsteht nun aus A displaystyle A nbsp indem hinreichend grosse Abschnitte aus A displaystyle A nbsp entfernt werden sodass A displaystyle A nbsp nicht polynomiell auf B displaystyle B nbsp reduziert werden kann B displaystyle B nbsp aber trotzdem noch nicht in P liegt Zur Konstruktion wird eine polynomiell berechenbare Funktion g displaystyle g nbsp definiert die zu jedem Schritt x displaystyle x nbsp der Konstruktion angibt welche Anforderung gerade verfolgt wird Dann liegen genau die Elemente x displaystyle x nbsp in B displaystyle B nbsp sodass in Schritt x displaystyle left x right nbsp eine Anforderung der Form 2 e displaystyle 2e nbsp verfolgt wurde B x A g x gerade displaystyle B x in A g left x right text gerade nbsp Somit lasst sich B displaystyle B nbsp uber folgende Funktion f displaystyle f nbsp polynomiell auf A displaystyle A nbsp many one reduzieren f x x wenn g x gerade a sonst displaystyle f x begin cases x amp text wenn g left x right text gerade a amp text sonst end cases nbsp wobei a A displaystyle a notin A nbsp ein beliebiges Element ist Als erste Anforderung wird g 0 0 displaystyle g 0 0 nbsp gewahlt Fur s gt 0 displaystyle s gt 0 nbsp wird g s displaystyle g s nbsp induktiv so definiert dass es in Polynomzeit berechnet werden kann Man beginnt nacheinander die Werte g 0 g 1 g s 1 displaystyle g 0 g 1 dots g s 1 nbsp zu berechnen und bricht nach s displaystyle s nbsp Berechnungsschritten ab n displaystyle n nbsp sei die grosste Zahl sodass g n displaystyle g n nbsp in s displaystyle s nbsp Schritten bestimmen werden kann Dann gibt es zwei Falle g n 2 e displaystyle g n 2e nbsp Man sucht ein Wort z displaystyle z nbsp mit B z T e z displaystyle B z neq T e z nbsp Da g displaystyle g nbsp polynomiell in s displaystyle s nbsp berechenbar sein soll werden nur die ersten s displaystyle s nbsp Berechnungsschritte der Suche ausgefuhrt Wird dabei ein z displaystyle z nbsp gefunden ist R 2 e displaystyle R 2e nbsp erfullt Dann ist g s g n 1 2 e 1 displaystyle g s g n 1 2e 1 nbsp Sonst ist nicht bekannt ob R 2 e displaystyle R 2e nbsp schon erfullt wurde und g s g n displaystyle g s g n nbsp um weiterhin zu versuchen R 2 e displaystyle R 2e nbsp zu erfullen g n 2 e 1 displaystyle g n 2e 1 nbsp Man sucht ein Wort z displaystyle z nbsp mit A z T e B z displaystyle A z neq T e B z nbsp Analog zu 2 e displaystyle 2e nbsp werden nur s displaystyle s nbsp Schritte durchgefuhrt Findet man ein z displaystyle z nbsp ist R 2 e 1 displaystyle R 2e 1 nbsp erfullt und g s g n 1 2 e 1 displaystyle g s g n 1 2 e 1 nbsp Sonst ist nicht bekannt ob R 2 e 1 displaystyle R 2e 1 nbsp schon erfullt wurde und g s g n displaystyle g s g n nbsp um weiterhin zu versuchen R 2 e 1 displaystyle R 2e 1 nbsp zu erfullen Zu zeigen ist nun dass alle Anforderungen erfullt werden Dazu genugt es zu zeigen dass g displaystyle g nbsp surjektiv ist Angenommen es gibt ein n displaystyle n nbsp mit g n g m displaystyle g n g m nbsp fur alle m gt n displaystyle m gt n nbsp Ist g n R 2 e displaystyle g n R 2e nbsp ware B displaystyle B nbsp polynomiell entscheidbar obwohl es sich nur auf endlich vielen Wortern von A P displaystyle A notin mathbf P nbsp unterscheidet Ist g n R 2 e 1 displaystyle g n R 2e 1 nbsp ware B displaystyle B nbsp endlich Da A displaystyle A nbsp aber nicht in P displaystyle mathbf P nbsp liegt lasst es sich nicht auf eine endliche Sprache reduzieren Literatur BearbeitenSanjeev 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 XWeblinks BearbeitenLance Fortnow Two Proofs of Ladner s Theorem PDF Datei 72 kB Einzelnachweise Bearbeiten a b Odifreddi 1999 S 191 Abgerufen von https de wikipedia org w index php title Satz von Ladner amp oldid 153120553