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

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".) $io$ $SUBEXP$ $L$ $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ $n$ $L$ $L'$ $n$

Gibt es ein Orakel , das - ? Wenn wir SAT wie gewohnt mit dem Orakel ausstatten , können wir dann sagen, dass nicht zu dieser Klasse gehört? $A$ $NP^A \not\subset io$ $SUBEXP^A$ $A$ $SAT^A$

(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$ $C$

cc.complexity-theory sat oracles Ryan Williams
quelle

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

vzn

Antworten:

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. $^A$ $^A$ $^A$ $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$

Lance Fortnow
quelle

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)

EXP⊈io $EXP \nsubseteq io$

SUBEXP $SUBEXP$

TIME(f(n))⊈io $TIME(f(n)) \nsubseteq io$

für geeignete Funktionen f (n) und (2)

impliziert

(oder mindestens

)? TIME(f(n)log(f(n))) $TIME(\frac{f(n)}{\log(f(n))})$

NP⊆io $NP \subseteq io$

P $P$

P=NP $P = NP$

NP⊆P/poly $NP \subseteq P/ poly$

Michael Wehar

Ich vermute, meine größte Verwirrung ist, warum nicht jedes

Problem einen

Algorithmus hat, der das Problem nur für einen Satz von Eingabelängen

mit

löst ist ein

selbst eingestellt. EXP $EXP$

Complete $Complete$

io $io$

SUBEXP $SUBEXP$

X $X$

EXP $EXP$

Complete $Complete$

Michael Wehar

Mit anderen Worten, die

ist Algorithmus hilft uns nicht , weil wir müssten entscheiden ,

, um zu wissen , wie das verwenden

- Algorithmus. Es würde mich jedoch nicht wundern, wenn die von Ihnen oder anderen geleistete Arbeit meine Anfrage löst. io $io$

SUBEXP $SUBEXP$

X $X$

io $io$

SUBEXP $SUBEXP$

Michael Wehar

@ RyanWilliams Hallo Ryan, irgendwelche Gedanken? Vielen Dank für Ihre Zeit. :)

Michael Wehar

@ 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

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

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