Kann ein zufälliges Orakel ändern, welche TFNP-Probleme im Durchschnitt stark sind?

9

Ich habe zu
verschiedenen Zeiten über die folgende Frage nachgedacht, seit ich diese Frage zur Kryptographie gesehen habe .


Frage

Sei eine TFNP- Beziehung. Kann ein zufälliges Orakel P / Poly helfen , R mit nicht zu vernachlässigender Wahrscheinlichkeit zu brechen ? Formaler, R
R

Tut

für alle P / poly Algorithmen , Pr x [ R ( x , A ( x ) ) ] ist vernachlässigbarAPrx[R(x,A(x))]

implizieren das unbedingt

für fast alle o racles , für alle P / poly Oracle-Algorithmen A , Pr x [ R ( x , A O ( x ) ) ] ist vernachlässigbarOAPrx[R(x,AO(x))]

?


Alternative Formulierung

Die relevante Menge von Orakeln ist Gδσ (also messbar). Wenn Sie also kontrapositiv sind und Kolmogorovs Null-Eins-Gesetz anwenden , entspricht die folgende Formulierung der ursprünglichen.

Tut

für fast alle o racles , es existiert ein P / poly Oracle-Algorithmus A , so daß Pr x [ R ( x , A O ( x ) ) ] ist nicht vernachlässigbarO
APrx[R(x,AO(x))]

implizieren das unbedingt

Es gibt einen P / Poly-Algorithmus so dass Pr x [ R ( x , A ( x ) ) ] nicht vernachlässigbar istAPrx[R(x,A(x))]

?


Der einheitliche Fall

Hier ist ein Beweis für die einheitliche Version :

Es gibt nur countably-many PPT Oracle-Algorithmen, so durch zählbare Additivität der null [ideal] [8], ein PPT - Algorithmus ist , so dass für einen nicht - Null - Satz von Orakeln O , Pr x [ R ( x , A O ( x ) ) ] ist nicht zu vernachlässigen. Sei B ein solcher Orakel-Algorithmus.AO
Prx[R(x,AO(x))]B

In ähnlicher Weise lassen eine positive ganze Zahl sein , so dass für einen nicht-Null - Satz von Orakeln O , Pr x [ R ( x , B O ( x ) ) ] ist unendlich oft mindestens n - c , wobei n die Länge die Eingabe. Durch die contra von Borel-Cantelli , & Sigma; n = 0 Pr O [ n - cPr x { 0 , 1cO
Prx[R(x,BO(x))]ncn
ist unendlich.n=0PrO[ncPrx{0,1}n[R(x,BO(x))]]

Durch den Vergleichstest ist unendlich oft .PrO[ncPrx{0,1}n[R(x,BO(x))]n2

Sei der PPT-Algorithmus, der [das Orakel simuliert] [12] und B mit diesem simulierten Orakel ausführt.SB

Fixiere und sei G o o d die Menge der Orakel O, so dass n - cPr x { 0 , 1 } n [ R ( x , B O ( x ) ) ] .nGoodOncPrx{0,1}n[R(x,BO(x))]

Wenn nicht null ist, dann ist Pr O [ OG o o d ] n - c = Pr O [ OG o o d ] E O [ n - c ] Pr O [ OG o o d ] E O [ Pr x { 0Good .

PrO[OGood]nc=PrO[OGood]EO[nc]PrO[OGood]EO[Prx{0,1}n[R(x,BO(x))]OGood]=EO[Prx{0,1}n[OGood and R(x,BO(x))]]EO[Prx{0,1}n[R(x,BO(x))]]=PrO,x{0,1}n[R(x,BO(x))]=Prx{0,1}n,O[R(x,BO(x))]=Ex{0,1}n[PrO[R(x,BO(x))]]=Ex{0,1}n[Pr[R(x,S(x))]]=Prx{0,1}n[R(x,S(x))]

Da unendlich oft ist, ist Pr x [ R ( x , S ( x ) ) ] nicht vernachlässigbar.PrO[OGood]n2Prx[R(x,S(x))]

Daher gilt die einheitliche Version . Der Beweis nutzt kritisch die Tatsache, dass es
nur zählbar viele PPT- Orakel-Algorithmen gibt. Diese Idee funktioniert im
ungleichmäßigen Fall nicht, da es kontinuierlich viele P / Poly-Orakel-Algorithmen gibt.

Gemeinschaft
quelle
ORAAAA
ORA
1
@Adam, es gibt einen anderen Quantifizierer, der wichtig ist. Ich denke, es ist einfacher, die Negation zu betrachten: Ist es möglich, dass es für fast jedes Orakel einen ungleichmäßigen Gegner gibt, der das Orakel verwenden kann, um das Suchproblem zu lösen?
Kaveh
Aha. Ich beantwortete eine andere Frage. Entschuldigung für die Verwirrung.
Adam Smith
@domotorp: Sie sollten jetzt behoben werden. (Meine beste Vermutung, warum das passiert ist, ist dieVerwendung von nummerierten Links , anstatt in-line Links).

Antworten:

0

Nein zu meinem Titel und Ja zum Text meiner Frage. Dies verallgemeinert sich in der Tat sofort
auf jedes Spiel mit Polynomlänge, bei dem der Code der Gegner nicht verwendet wird.


CA

O
CPrx[R(x,CO(x))]


O

Prx{0,1}n[R(x,CO(x))]1/(nd)

O
Prx{0,1}n[R(x,CO(x))]1/(nd)

Sei j eine solche Anzeige und sei z der (nicht unbedingt effiziente) Orakelalgorithmus, der
n als Eingabe verwendet und die lexikographisch kleinste Orakelschaltung mit einer Größe von höchstens j + n ausgibtj
Prx{0,1}n[R(x,CO(x))]1/(n2)<ProbO[1/(nj)<Prx{0,1}n[R(x,(zO)O(x))]]für unendlich viele n.


Für solche n,

1/(n2+j)=1/((n2)(nj))=(1/(n2))(1/(nj))<ProbO,x{0,1}n[R(x,(zO)O(x))]




An

x

y


A
1/(n2+j)<ProbO[AO(n,zO(n))].
Sei p wie in Satz 2 und setzef=2p(j+nj)n(2+j)2


SP
1/(n2+j)<ProbO[AO(n,zO(n))] dann

1/(2(n2+j))=(1/(n2+j))(1/(2(n2+j)))=(1/(n2+j))1/(22(n(2+j)2))
=(1/(n2+j))(p(j+nj))/(22p(j+nj)(n(2+j)2))=(1/(n2+j))(p(j+nj))/(2f)
<ProbO[AO(n,zO(n))](p(j+nj))/(2f)ProbO[AP(n,zO(n))].


Für n so dass1/(n2+j)<ProbO[AO(n,zO(n))]::

[Cj]
[]
A11/(2(n2+j))
j

Aj
1/(2(n2+j))j1/(2(n2+j))1/(2(n2+j))1/(2(n2+j))


1/(n2+j)<ProbO[AO(n,zO(n))], es gibt also ein Polynom, so dass

die Sequenz, deren n-ter Eintrag die lexikographisch kleinste
[Schaltung C der Größe, die oben durch dieses Polynom begrenzt ist] ist, die maximiertPrx{0,1}n[R(x,C(x))]

ist ein P / Poly-Algorithmus, dessen Wahrscheinlichkeit (über die Wahl von x), eine Lösung zu finden, nicht vernachlässigbar ist.


Daher gilt die Implikation im Körper meiner Frage immer.


A


quelle