He estado pensando en la siguiente pregunta en
varias ocasiones desde que vi esta pregunta sobre Criptografía .
Pregunta
Sea una relación TFNP . ¿Puede un oráculo aleatorio ayudar a P / poly
a romper con una probabilidad no despreciable? Más formalmente,
Hace
para todos los algoritmos P / poly , es insignificante
implica necesariamente que
para casi todos o racles , para todos P / oracle-algoritmos de poli , es insignificante
?
Formulación alternativa
El conjunto relevante de oráculos es (por lo tanto medible), por lo tanto, al tomar contrapositivo y aplicar la ley cero uno de Kolmogorov , la siguiente formulación es equivalente a la original.
Hace
para casi todos los o racles , existe un algoritmo P / poly oracle tal que no es despreciable A Pr x [ R ( x , A O ( x ) ) ]
implica necesariamente que
existe un algoritmo P / poli tal que no es despreciablePr x [ R ( x , A ( x ) ) ]
?
El caso uniforme
Aquí hay una prueba de la versión uniforme :
Solo hay muchos algoritmos de oráculo PPT, por lo que mediante la aditividad contable del nulo [ideal] [8], hay un algoritmo PPT tal que para un conjunto no nulo de oráculos ,
no es despreciable. Deje que sea un algoritmo de oráculo.O Pr x [ R ( x , A O ( x ) ) ] B
Del mismo modo, supongamos que sea un número entero positivo de modo que para un conjunto no nulo de oráculos ,
es infinitamente frecuente al menos , donde es la longitud de la entrada.
Por el contrapositivo de Borel-Cantelli ,
es infinito.O Pr x [ R ( x , B O ( x ) ) ] n - c n ∑ ∞ n = 0 Pr O [ n - c ≤ Pr x ∈ { 0 , 1 } n [ R ( x , B O ( x ) ) ] ]
Por la prueba de comparación , infinitamente a menudo .
Sea el algoritmo PPT que [simula el oráculo] [12] y ejecuta con ese oráculo simulado.B
Arregle deje que sea el conjunto de oráculos tal que .G o o d O n - c ≤ Pr x ∈ { 0 , 1 } n [ R ( x , B O ( x ) ) ]
Si no es nulo, entonces .Pr O [ O ∈ G o o d ] ⋅ n - c = Pr O [ O ∈ G o o d ] ⋅ E O [ n - c ] ≤ Pr O [ O ∈ G o o d ] ⋅ E O [ Pr x ∈ { 0 , 1 } n
Como infinitamente seguido, no es despreciable.
Por lo tanto, la versión uniforme es válida. La prueba utiliza críticamente el hecho de que
solo hay contablemente muchos algoritmos de oráculo PPT . Esta idea no funciona en el caso
no uniforme, ya que hay muchos algoritmos continuos de P / poli oracle.
Respuestas:
Tenga en cuenta que usaré para los adversarios, en lugar de , para que coincida con la notación del Teorema 2 .
Suponga que para casi todos los oráculos , existe un algoritmo P / poli oracle tal que no es despreciable.O
C Prx[R(x,CO(x))]
Para casi todos los oráculos , existe un número entero positivo d tal que existe una secuencia de circuitos de tamaño como máximo d + n d tal que es infinitamente mayor que .O
Prx∈{0,1}n[R(x,CO(x))] 1/(nd)
Por aditividad contable, existe un entero positivo d tal que para un conjunto no nulo de oráculos , existe una secuencia de circuitos de tamaño como máximo d + n d tal que es infinitamente mayor que .O
Prx∈{0,1}n[R(x,CO(x))] 1/(nd)
Deje que j sea tal anuncio, y deje que z sea el algoritmo de oráculo (no necesariamente eficiente) quej
Prx∈{0,1}n[R(x,CO(x))] 1/(n2)<ProbO[1/(nj)<Prx∈{0,1}n[R(x,(zO)O(x))]] por infinitamente n.
toma n como entrada y produce el menor circuito oráculo lexicográficamente de tamaño como máximo j + n que maximiza . Por el contrapositivo de Borel-Cantelli ,
Para tal n,
.
A n
Sea el algoritmo oracle que toma 2 entradas, una de las cuales es , y hace lo siguiente:
Elija una cadena aleatoria de n bits . Intente [analizar la otra entrada como un circuito oracle y ejecutar ese circuito oracle en la cadena de n bits]. Si eso tiene éxito y la salida del circuito del oráculo satisface R (x, y), entonces la salida 1, o bien la salida 0. (Tenga en cuenta que no es solo el adversario). Para infinitamente n, . Deje p ser como en el Teorema 2 , y establezcax
y
A
1/(n2+j)<ProbO[AO(n,zO(n))]
f=2⋅p⋅(j+nj)⋅n(2+j)⋅2 .
S P
1/(n2+j)<ProbO[AO(n,zO(n))]
Según el teorema 2 , existe una función oracle tal que con como en ese teorema, sientonces
Para n tal que:
En particular, existe un circuito de oráculo de tamaño como máximo j + n y una asignación de longitud como máximo f tal que con esa entrada y de premuestreo, probabilidad de dar salida a 's es mayor que . Los circuitos de tamaño de Oracle como máximo j + n se pueden representar con bits poly (n), por lo que para p está limitado por un polinomio en n, lo que significa que f también está limitado por encima por un polinomio en n.[ C j]
[ ]
A 1 1/(2⋅(n2+j)) j
A 1j
1/(2⋅(n2+j)) 1j bits, las entradas pre-muestreadas más largas que eso pueden ignorarse, por lo que tal muestreo previo puede simularse de manera eficiente y perfecta con un oráculo aleatorio y bits codificados de poli (n). Eso significa que hay circuitos de oráculo de tamaño polinómico de tal manera que con un oráculo aleatorio estándar, la probabilidad de que los circuitos encuentren una solución es mayor que . Tal oráculo aleatorio puede a su vez ser eficiente y perfectamente simulado con bits aleatorios ordinarios, por lo que hay circuitos probables de tamaño polinómico no oráculo cuya probabilidad de encontrar una solución es mayor que 11/(2⋅(n2+j)) 11/(2⋅(n2+j)) . A su vez, al codificar la aleatoriedad óptica, hay circuitos deterministas de tamaño polinómico (no oráculo) cuya probabilidad (por encima de la elección de x) de encontrar una solución es mayor que .
Como se mostró anteriormente en esta respuesta, hay infinitos n n tales que, 11/(2⋅(n2+j))
1/(n2+j)<ProbO[AO(n,zO(n))] entonces hay un polinomio tal que
A
Por construcción de , eso significa que hay circuitos de oráculo de tamaño como máximo j + n y una asignación de longitud polinómica tal que cuando se ejecuta con ese muestreo previo, la probabilidad de que los circuitos encuentren una solución es mayor que . Dado que dichos circuitos no pueden realizar consultas más largas que j + n
la secuencia cuya enésima entrada es la menos lexicográficaPrx∈{0,1}n[R(x,C(x))]
[circuito C de tamaño limitado anteriormente por ese polinomio] que maximiza
es un algoritmo P / poli cuya probabilidad (sobre la elección de x) de encontrar una solución no es despreciable.
Por lo tanto, las implicaciones en el cuerpo de mi pregunta siempre son válidas.
Para obtener la misma implicación para otros juegos de longitud polinómica, soloA
cambie la prueba esta prueba para que los circuitos oráculo de entrada jueguen el juego.
fuente