Antecedentes
Se sabe que existe un oráculo A
A tal que, P S P A C E A ≠ P H APSPACEA≠PHA .Incluso se sabe que la separación es relativa a un oráculo aleatorio. Informalmente, uno puede interpretar que esto significa que hay muchos oráculos para los cuales P S P A C E
PSPACE y P HPH están separados.
Pregunta
Cómo complicados son estos oráculos que separan P S P A C E
PSPACE de P HPH . En particular, ¿hay un oráculo tal que ?A ∈ D T I M E ( 2 2 n ) P S P A C E A ≠ P H AA∈DTIME(22n) PSPACEA≠PHA ¿Tenemos algún oráculo tal que y tenga un límite superior de complejidad conocido?A P S P A C E A ≠ P H A A
A PSPACEA≠PHA A
Nota: la existencia de tal oráculo puede tener ramificaciones en la teoría de la complejidad estructural. Consulte la siguiente actualización a continuación para obtener más detalles.
Actualización con detalles sobre una técnica de límite inferior
Reclamación: Si , a continuación, para todos los oráculos , .P S P A C E = P H A ∈ P / p o l y P S P A C E A = P H A
Prueba Bosquejo: Supongamos que P S P A C E = P H
PSPACE=PH .Deja un oráculo A ∈ P / p o l y
A∈P/poly ser dada. Podemos construir un tiempo polinomial Σ 2Σ2 oracle Turing machine MM que para una longitud dada nn , adivina un circuito de tamaño p ( n )p(n) usando una cuantificación existencial y verifica que el circuito decide AA comparando la evaluación del circuito y el resultado de la consulta para cada longitud nn cadena utilizando una cuantificación universal.Además, considere un problema de decisión al que me refiero como circuito booleano cuantificado (QBC) donde se le da un circuito booleano cuantificado y desea saber si es válido (similar a QBF). Este problema es PSPACE completo porque QBF es PSPACE completo.
Por supuesto, se sigue que QBC ∈ P H . Digamos Q B C ∈ Σ k para algunos k suficientemente grandes. Deje N denotar un tiempo polinomial Σ k Máquina de Turing que resuelve QBC.
∈PH QBC∈Σk k N Σk Podemos entremezclan el cálculo de M y N (similar a lo que se hace en la demostración del teorema Karp-Lipton) para obtener un polinomio tiempo Σ k máquina de Turing oráculo que resuelve Q B C A .
M N Σk QBCA Informalmente, esta nueva máquina toma como entrada un QBC de Oracle (que es un QBC con puertas Oracle). Luego, calcula un circuito que calcula A en entradas de longitud n (separando simultáneamente los dos primeros cuantificadores). A continuación, que reemplaza las puertas Oracle en el QBC oráculo con el circuito para A . Finalmente, se procede a aplicar el resto del tiempo polinomial Σ k algoritmo para resolver Q B C en esta instancia modificada.
A n A Σk QBC
Ahora, podemos mostrar el límite inferior condicional.
Corolario: si existe un oráculo A ∈ N E X P tal que P S P A C E A ≠ P H A , entonces N E X P ⊈ P / p o l y .
Prueba Bosquejo: Supongamos que existe tal que P S P A C E A ≠ P H A . Si N E X P ⊆ P / p o l y , entonces obtendríamos una contradicción.A ∈ N E X P
A∈NEXP PSPACEA≠PHA NEXP⊆P/poly En particular, si N E X P ⊆ P / p o l y , a continuación, por la reivindicación anterior tenemos P S P A C E ≠ P H . Sin embargo, se sabe que la N E X P ⊆ P / p o l y implica que P S P A C E = P H .
NEXP⊆P/poly PSPACE≠PH NEXP⊆P/poly PSPACE=PH (vea aquí algunos detalles sobre los resultados conocidos de P / poly)
fuente
Respuestas:
Creo que si trazas el argumento dado, por ejemplo, en la Sección 4.1 de la encuesta de Ker-I Ko , obtienes un límite superior de D T I M E ( 2 2 O ( n 2 ) ) . De hecho, podemos reemplazar n 2 aquí con cualquier función n f ( n ) donde f ( n ) → ∞ como n → ∞ . Esto no es exactamente lo que se pidió, pero está cerca.DTIME(22O(n2)) n2 nf(n) f(n)→∞ n→∞
En particular, usando la traducción entre las separaciones de oráculo y los límites inferiores del circuito, y siguiendo la notación de Ko, tenemos lo siguiente:
Diagonalizaremos sobre cadenas de longitud t ( n ) = p n ( m ( n ) ) donde p n ( x ) = x n + n es "el" polinomio n -ésimo (en alguna enumeración de algoritmos de poli-tiempo) y m ( n ) se especificará a continuación.t(n)=pn(m(n)) pn(x)=xn+n n m(n)
Traduciendo a los límites inferiores del circuito, esto significa que estamos considerando circuitos de profundidad limitada en entradas de 2 t ( n ) .2t(n)
El requisito (ver p. 15 de Ko) necesitamos m ( n ) para satisfacer 1m(n) 10 2m/(d-1)>dpn(m(n))para todos losn. Aquídes la profundidad de los circuitos contra los que queremos diagonalizar, o equivalentemente el nivelΣ p d dePH contra elque queremos diagonalizar. Para diagonalizar contra todoPH, simplemente elijadpara que sea una función denque seaω(1); podemos elegir tald1102m/(d−1)>dpn(m(n)) n d Σpd PH PH d n ω(1) d sin embargo, eso crece arbitrariamente lento (tal vez sujeto a un supuesto de computabilidad en d ( n ) , pero eso no debería ser un obstáculo). Si suponemos que d ( n ) es constante (aunque no lo sea, pero crecerá arbitrariamente lentamente), entonces vemos que m ( n ) alrededor de 2 n debería funcionar.d(n) d(n) m(n) 2n
Esto significa que t ( n ) ∼ 2 n 2 , por lo que estamos buscando un límite inferior contra circuitos con entradas ∼ 2 2 n 2 .t(n)∼2n2 ∼22n2
Trevisan y Xue (CCC '13) demostraron que se puede encontrar una asignación en la que un circuito de profundidad acotada determinada en N entradas no calcula PARIDAD con una semilla de longitud de p o l y l o g ( N ) .N polylog(N)
Para nosotros N = 2 2 n 2 , entonces p o l y l o g ( N ) = 2 O ( n 2 ) . Podemos aplicar fuerza bruta sobre esas semillas en 2 2 O ( n 2 ) y usar la primera que funcione.N=22n2 polylog(N)=2O(n2) 22O(n2)
Para reemplazar el n 2 con n f ( n ) , simplemente deje que p n ( x ) = x f ( n ) + f ( n ) en su lugar.n2 nf(n) pn(x)=xf(n)+f(n)
Curiosamente, si estoy entendiendo correctamente, creo que esto implica que si uno pudiera mejorar el Trevisan-Xue ...
... a un algoritmo pseudodeterminista / Bellagio (ver el comentario de Andrew Morgan a continuación), uno obtendría que B P E X P ⊈ P / p o l y ; oBPEXP⊈P/poly
... a un algoritmo no determinista que adivinó los bits p o l y l o g ( N ) pero luego se ejecutó en el tiempo p o l y ( N ) , y tal que en cualquier ruta de aceptación produce la misma salida ( cf. N P S V ), implicaría N E X P ⊈ P / p o l y ; opolylog(N) poly(N) NPSV NEXP⊈P/poly
... para un algoritmo determinista, uno obtendría E X P ⊈ P / p o l y .EXP⊈P/poly
Por un lado, esto sugiere por qué desrandomizar aún más el lema de conmutación debería ser difícil, ¡un argumento que no estoy seguro se sabía antes! Por otro lado, esto me parece una especie de versión interesante de la dureza versus la aleatoriedad (¿o es esto realmente algo nuevo, oráculos versus aleatoriedad?).
fuente