Ist die Relativierung gut definiert?

Nach BGS - Theorem [1], gibt es eine Oracle , so dass . $A$ $P^A\neq NP^A$

Wenn die Relativierungsoperation eine genau definierte Funktion wäre, würde man erwarten, dass man aus schließen könnte, dass , z. B. , daraus folgen würde BGS. Allerdings ist noch offen. $B\mapsto B^A$ $B^A\neq C^A$ $B\neq C$ $P\neq NP$ $P\neq NP$

Bedeutet das, dass die Relativierung keine genau definierte Funktion ist?

Wenn ja, haben wir ein Beispiel für zwei nachweislich unterschiedliche Relativierungen derselben Komplexitätsklasse?

[1] TP Baker, J. Gill und R. Solovay, "Relativierungen der P =? NP-Frage"

cc.complexity-theory oracles relativization Michael
quelle

Baker-Gill-Solovay zeigt zwei Orakel: eines, bei dem P und NP gleich sind, und eines, bei dem sie nicht gleich sind. Das beantwortet deine letzte Frage.

Suresh Venkat

@ SureshVenkat: Wenn du meinst, dass es Orakel

A, B

$A,B$ so dass

und

dann ist dieses Ergebnis (Ladners Theorem?) Tatsächlich der Hintergrund meiner Frage. Ich kann sehen, warum

nicht

impliziert , aber ich verstehe nicht, warum

nicht

impliziert .

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P^{B} = N P^{B}

$P^B=NP^B$

P^{B} = N P^{B}

$P^B=NP^B$

P = N P

$P=NP$

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P \neq N P

$P\neq NP$

Michael

@Kaveh wäre hilfreich, um auf bestimmte Antworten zu verweisen. Ich habe die Fragen schnell gescannt und nichts gesehen.

Suresh Venkat

PS: Die kurze Antwort auf Ihre Frage lautet, dass eine Relativierung kein Erweiterungs- / Funktionsoperator für die Klasse von Problemen ist, auch wenn die Notation etwas anderes impliziert. Es gibt keine allgemeine Definition der Relativierung für Problemklassen, Relativierungen sind für Maschinenmodelle definiert und ein einzelnes Maschinenmodell kann mehrere verschiedene relativierte Versionen haben.

Kaveh

fyi fortnow stellt in seiner Zusammenfassung fest / gibt zu, dass Komplexitätstheoretiker Relativierung sowohl verwenden als auch "missbrauchen" .... es scheint zuweilen eine zugegebenermaßen graue Zone der Komplexitätstheorie zu sein ....

vzn

Antworten:

Du bist genau richtig. Die Relativierungsoperation ist nicht gut definiert. P und P ^A sind unabhängig definierte Objekte. Die Namen sind suggestiv, aber Sie können P ^A nicht formal aus der Menge P definieren. (Sie können P aus P ^A definieren, indem Sie A als leere Menge festlegen.) $B\mapsto B^A$

Denken Sie an P ^A als eine Art Verallgemeinerung von P zu sein, die P gleich , wenn A leer ist, aber ansonsten kann unterschiedlich sein. Nun , wenn Sie nur die Menge P wissen, ist es nicht klar , wie dies zu verallgemeinern P erhalten ^A . Wenn ich Sie analog dazu auffordere, die reellen Zahlen zu verallgemeinern, ist nicht klar, nach welcher Verallgemeinerung ich suche. Denke ich an Felder, Ringe, Vektorräume usw.? Der Grund dafür ist, dass P lediglich eine Menge von Sprachen ist, P ^A jedoch als Maschine definiert ist. Diese Maschine hat die Eigenschaft, dass wenn A leer ist, sie genau die gleichen Sprachen wie P entscheidet. Sie könnten sich eine andere Maschine einfallen lassen, nennen wir sie Q ^A , die auch die Eigenschaft hat, dass wenn A leer ist, die gleichen Sprachen wie P entscheidet Dies bedeutet nicht, dass P.^A = Q ^A für alle A. Dies wäre analog zu der Behauptung, dass wenn f (0) = g (0) ist, f und g dieselbe Funktion sind.

Vielleicht ist dieser Beitrag von Terence Tao hilfreich.

Robin Kothari
quelle

Danke, Robin. Das ist eine weitere gute Antwort, und der Link zu Taos Artikel ist sehr hilfreich.

Suresh Venkat

(Ich gehe davon aus, dass diese Frage irgendwann nach CS.SE migriert wird, aber ich veröffentliche meine Antwort vorerst hier auf cstheory.)

Technisch betrachtet man Relativierung normalerweise nicht als "Operator" oder "Funktion"; Ich sehe jedoch keinen Grund, warum Sie eine Aussage nicht nehmen und die Aussage einer relativierten Version davon zuordnen konnten.

Der Trick ist, dass, wie andere gesagt haben, die Relativierung nicht wirklich über eine Komplexitätsklasse definiert ist; Stattdessen wird es in dem von Ihnen verwendeten Berechnungsmodell definiert. Was weiter relativiert, ist die Aussage, nicht die Klassen. (Die Notation ist etwas irreführend.)

Ein Beispiel dafür ist, dass ich theoretisch sagen könnte, dass eine Aussage relativiert (oder weniger wahrscheinlich nicht relativiert), selbst wenn sie sich überhaupt nicht auf eine Turing-Maschine bezieht. Zum Beispiel könnte ich (wahrheitsgemäß) sagen, dass "1 + 1 = 2" relativiert, weil relativ zu jedem Orakel, das zur Definition meiner universellen Turing-Maschine hinzugefügt werden könnte, 1 + 1 = 2 wahr bleiben würde.

Die kurze Antwort lautet also: Ja, es ist gut definiert, aber nicht für Klassen.

Philip White
quelle

P^{A} \neq N P^{A}

$P^A \ne NP^A$

P = N P

$P = NP$

A

$A$

Darauf habe ich in meiner Antwort eingegangen ... Ich sagte, man kann nicht über Klassen relativieren, man relativiert über Aussagen. Die Fähigkeit, über P und NP zu relativieren, verschwindet, wenn Sie nicht über Klassen einzeln relativieren können. Das Argument funktioniert nicht, wenn ich nur sage "Ich habe eine Aussage relativiert, jetzt die Relativierung invertiert und sie sollte immer noch" nicht mehr als möglich sein (am Beispiel der Funktion f (x) = x ^ 2) ". 5 ^ 2 ist zusammengesetzt "->" 5 ist zusammengesetzt. "

Philip White

Es gibt keine allgemeine Definition der Relativierung von Aussagen. Es gibt nur relativierte Rechenmodelle. Die Relativierung von P gegen NP setzt voraus, dass wir die relativierten Modelle von P und NP zuvor festgelegt haben.

Kaveh