Relativieren sich die Beweise, dass Permanent nicht in Uniform

15

Dies ist eine Antwort auf diese Frage und steht im Zusammenhang mit dieser Frage von Shiva Kinali.

Es scheint, dass die Beweise in diesen Arbeiten ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) Hierarchiesätze verwenden. Ich möchte wissen, ob es sich bei den Beweisen um " reine " Diagonalisierungssätze handelt oder ob sie etwas anderes als die übliche Diagonalisierung verwenden. Also meine Frage ist

es eine vernünftige Relativierung, die Uniform dauerhaft macht ?TC0

Beachten Sie, dass ich nicht sicher bin, wie ich den Oracle-Zugriff für uniform soll. Ich weiß, dass es nicht , die richtige Definition für kleine Komplexitätsklassen zu finden. Eine andere Möglichkeit ist, dass permanent für im relativierten Universum nicht vollständig ist. In diesem Fall sollte ich ein vollständiges Problem für im relativierten Universum anstelle dessen verwenden, und ich denke sollte in jedem vernünftigen relativierten Universum ein vollständiges Problem haben. # P # P # PTC0#P#P#P

Kaveh
quelle
1
Wie definieren Sie eine relativierte Version der bleibenden Karte? Oder suchen Sie eine relativierte Welt, in der PP⊆TC ^ 0?
Tsuyoshi Ito
@ Tsuyoshi: Das Problem ist, dass ich mir nicht sicher bin, ob der Beweis, dass die bleibende Karte vollständig ist, für . Es scheint mir , dass der Beweis , dass dauerhaft nicht in der Uniform T C 0 auch für jedes anderes vollständiges Problem funktioniert. Eine vernünftige Relativierung, die s h a r p P in T C 0 setzt, würde meine Frage beantworten. sheinrpPTC0sheinrpPTC0
Kaveh
2
Ich bin mir nicht sicher, was Sie unter "vernünftiger" Relativierung verstehen. Für zwei beliebige Komplexitätsklassen kann man sie gleich machen, indem man ein Orakel nimmt, das stark genug ist, oder? Beispiel . (Die erste Klasse ist A C 0 mit "QBF Tore".)EINC0PSPEINCE=PSPEINCE=PSPEINCEPSPEINCEEINC0
Ryan Williams
@ Ryan: Ich dachte, dass die Art und Weise, wie man den Oracle-Zugriff definiert, wichtig ist, und wenn die Definition nicht richtig ist, können seltsame Dinge passieren. Siehe zum Beispiel cs.toronto.edu/~sacook/homepage/rel-web.ps . (Anmerkung: Ich erinnere mich nicht, dass sie auch besprechen .) Eine Maschine mit mehr Ressourcen kann kompliziertere Fragen stellen als eine eingeschränktere aus demselben Orakel, und das ist der Grund, warum wir keine (vernünftige) haben ) Relativierung, die DTime (n) = DTime ( n 2 ) ergeben würde, also scheint es mir, dass es nicht so einfach ist, wie Sie sagen, oder? TC0n2
Kaveh
(logarithmische Zeithierarchie)P H P S p aAC0=LH , so sollte es keine vernünftige Relativierung seindas machen würde , A C 0 = P S p a c e . Ich habe das Gefühl, dass etwas mit meiner Argumentation in der vorherigen Zeile nicht stimmt. Wissen wir, L H P H ? PHPSpaceAC0=PSpaceLHPH
Kaveh

Antworten:

17

Jede Trennung von Klassen, die unter "Polynomressourcen" geschlossen wurden, hat ein Orakel, das sie gleich macht. (Vorausgesetzt, der Orakelmechanismus ist fair und beide Maschinenmodelle können polynomielle Längenabfragen durchführen und nicht mehr.)

Sei " T C 0 mit Toren für Orakel O ". Wenn O eine P S P A C E -komplette Sprache unter T C 0 -Reduktionen ist, haben wir T C 0 O = P S P A C E = P S P A C E O = P P O , wo im Orakelmechanismus für P S PTC0ÖTC0ÖÖPSPEINCETC0TC0Ö=PSPEINCE=PSPEINCEÖ=PPÖ , wir zählen den Platzbedarf des Orakelbands zusammen mit dem Rest des Speichers. (Es werden also nur Abfragen mit polynomialer Länge gestellt.) Eine solche Gleichheit gilt für viele Klassen, die "unter polynomialen Ressourcen geschlossen" sind, in dem Sinne, dass sie Abfragen mit polynomialer Länge an ein Orakel stellen können, jedoch nicht größer. Diese Klassen umfassen Dinge wie A C 0 , T C 0 , L O G S P A C E (unter einem anderen Orakelmechanismus, der keine Orakelabfragen in Bezug auf den begrenzten Raum berücksichtigt), P , N P , P H und PPSPEINCEEINC0TC0LÖGSPEINCEPNPPH . Jede Klassentrennung in dieser Liste muss daher notwendigerweise ein "nicht relativierendes" Argument verwenden. Dies impliziert auch (zum Beispiel), dass die natürlichen Beweise von Dingen wie Parität nicht in A C 0 nicht relativierend sind (aber das ist noch einfacher: Alles, was Sie hier brauchen, ist ein Orakel für Parität, so dass Sie A C 0 erhalten. [ 2 ] ).PPEINC0EINC0[2]

Ich glaube, dass die meisten der von Ihnen zitierten Beweise (wenn nicht alle) funktionieren, indem sie annehmen und einen Widerspruch herleiten. Diese Ergebnisse werden als "indirekte Diagonalisierung" bezeichnet. Eine Relativierung ihres Beweises müsste also lauten: "Wenn T C 0 O = P P O , dann Widerspruch ...", aber diese Annahme trifft tatsächlich auf einige Orakel O zu .TC0=PPTC0Ö=PPÖÖ

In den Kommentaren wurde darauf hingewiesen, dass in der Art und Weise, wie ich es benutze. Dies sind nur Feinheiten mit dem Orakelmechanismus. Auf der LOGSPACE-Seite kann das Abfrageband nicht Teil des gebundenen Speicherbereichs sein, da Abfragen eine polynomielle Länge haben. Auf der PSPACE Seite, die Abfrage Band istLÖGSPEINCEÖ=PSPEINCEÖals Teil des Raums gebunden genommen. Das sollte die Dinge "fair" machen. Aber wenn Sie ihnen genau den gleichen Orakelmechanismus geben, können Sie sie tatsächlich durch Diagonalisierung wieder trennen. Wenn beispielsweise Abfragen nicht zum begrenzten Speicherplatz zählen, können Sie in PSPACE ^ {PSPACE} exponentiell lange Fragen an PSPACE stellen, sodass diese tatsächlich EXPSPACE enthalten. Ich entschuldige mich dafür, dass ich das nicht ausdrücklich früher gesagt habe.

Die raumbegrenzte Berechnung ist in Bezug auf Orakel sehr subtil. Auf Seite 5 dieses Artikels von Fortnow finden Sie eine gute Zusammenfassung, warum sich Orakel und weltraumgebundene Berechnung nicht immer mischen.

Ryan Williams
quelle
2
Vielen Dank für den Kommentar zu PSPACE ^ {PSPACE} mit EXPSPACE in dem Modell, das wir für LOGSPACE verwendet haben. Meine Verwirrung wurde beseitigt.
Robin Kothari