Gibt es ein Orakel, bei dem SAT in subexponentieller Zeit nicht unendlich oft vorkommt?

30

Definiere - als die Klasse der Sprachen so dass es eine Sprache und für unendlich viele , und stimme in allen Fällen der Länge . (Das heißt, dies ist die Klasse von Sprachen, die "unendlich oft in subexponentieller Zeit gelöst werden kann".)i o S U B E X P L L 'ε > 0 T I M E ( 2 n ε ) n LioSUBEXPLLε>0TIME(2nε)nLLLnn

Gibt es ein Orakel , das - SUBEXP ^ A ist ? Wenn wir SAT wie gewohnt mit dem Orakel A ausstatten , können wir dann sagen, dass SAT ^ A nicht zu dieser Klasse gehört?A N P Ai o S U B E X P AANPA⊄ioSUBEXPAAASATASATA

(Ich stelle hier getrennte Fragen, weil wir mit unendlich vielen Zeitklassen vorsichtig sein müssen: Nur weil Sie eine Reduktion von Problem auf Problem und unendlich oft lösbar ist, erhalten Sie möglicherweise nicht wirklich, dass lösbar ist unendlich oft ohne weitere Annahmen zur Reduktion: Was ist, wenn Ihre Reduktion von die Eingangslängen "verfehlt", auf denen Sie lösen können ?)B C C B B CBCCBBC

Ryan Williams
quelle
1
scheint eine Erweiterung oder Variation der Idee von Baker Gill Solovay 1975 zu sein? Kann man das irgendwie kontrastieren?
vzn

Antworten:

26

Sie können einfach das Orakel A st NP = EXP da EXP nicht in io-subexp ist. Für SAT hängt es von der Codierung ab. Wenn beispielsweise die einzigen gültigen SAT-Instanzen eine gerade Länge haben, ist es einfach, SAT für Zeichenfolgen ungerader Länge zu lösen. Aber wenn Sie eine Sprache wie , sollten Sie in Ordnung sein.AAAAAAL={ϕ01 | ϕSATA}L={ϕ01 | ϕSATA}

Lance Fortnow
quelle
1
Haben Sie alle Verweise auf das Konzept der io Komplexitätsklassen und Trennungen in der Literatur. Insbesondere bin ich mir nicht ganz sicher, warum - . Haben wir zusätzlich (1) T I M E ( f ( n ) ) i o - T I M E ( f ( n )E X P i oEXPioSUBEXPSUBEXPTIME(f(n))iolog ( f ( n ) ) )für geeignete Funktionen f (n) und (2)NPio-PimpliziertP=NP (oder mindestensNPP/poly)? TIME(f(n)log(f(n)))NPioPP=NPNPP/poly
Michael Wehar
Ich vermute, meine größte Verwirrung ist, warum nicht jedes E X P - C o m p l e t e - Problem einen I O - S U B E X P - Algorithmus hat, der das Problem nur für einen Satz von Eingabelängen X mit X löst ist ein E X P - C o m p l e t e selbst eingestellt. EXPCompleteioSUBEXPXXEXPComplete
Michael Wehar
Mit anderen Worten, die i o - S U B E X P ist Algorithmus hilft uns nicht , weil wir müssten entscheiden , X , um zu wissen , wie das verwenden i o - S U B E X P - Algorithmus. Es würde mich jedoch nicht wundern, wenn die von Ihnen oder anderen geleistete Arbeit meine Anfrage löst. ioSUBEXPXioSUBEXP
Michael Wehar
@ RyanWilliams Hallo Ryan, irgendwelche Gedanken? Vielen Dank für Ihre Zeit. :)
Michael Wehar
1
@ RyanWilliams Danke für den Kommentar! Es hat geholfen und ich glaube, es hat geklappt. Nun, es scheint, dass das Argument überhaupt nicht von EXP abhing und dies könnte verallgemeinert werden, um so etwas wie (1) zu beweisen. Der entscheidende Punkt war jedoch "der entgegengesetzte Wert bei mindestens einem Eingang dieser Länge ". Mit anderen Worten, das Argument in meinem Kopf hängt davon ab, ob man sich auf unendlich viele Eingabelängen einigt (nicht einfach auf unendlich viele Eingaben). Ich habe immer noch keine Ahnung von so etwas wie (2). Nochmals vielen Dank und einen schönen Tag / Nacht. :)
Michael Wehar
16

Sie müssen nicht zu den Längen gehen, die Lance vorschlug. Beispielsweise ist es im Vergleich zu einem zufälligen Orakel exponentiell schwierig, das Orakel als Einwegfunktion zu verwenden (z. B. bei aufeinanderfolgenden Bitpositionen), auf allen bis auf endlich viele Längen zu invertieren.

Dieses Problem reduziert sich direkt auf SAT bei der Eingabe gleicher Länge, so dass SAT ^ A nicht unendlich oft unterbelichtet wird.

Russell Impagliazzo
quelle
1
Ich sollte sagen, dass die Anzahl der Eingänge für die Schaltung gleich ist und nicht die Gesamtgröße der Instanzen. Wenn Sie jedoch Schaltkreisgrößen durch Hinzufügen redundanter Klauseln auffüllen dürfen, sollten Sie in der Lage sein, jeden festen Eingangsgrößencode zu einer verwandten Einwegfunktion zu machen.
Russell Impagliazzo