¿Cuál es el oráculo de mínima complejidad que separa a PSPACE de la jerarquía polinómica?

17

Antecedentes

Se sabe que existe un oráculo AA tal que, P S P A C E AP H APSPACEAPHA .

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 EPSPACE y P HPH están separados.

Pregunta

Cómo complicados son estos oráculos que separan P S P A C EPSPACE 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 AP H AADTIME(22n)PSPACEAPHA

¿Tenemos algún oráculo tal que y tenga un límite superior de complejidad conocido?A P S P A C E AP H A AAPSPACEAPHAA

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 APSPACE=PHAP/polyPSPACEA=PHA

Prueba Bosquejo: Supongamos que P S P A C E = P HPSPACE=PH .

Deja un oráculo A P / p o l yAP/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.PHQBCΣkkNΣ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 .MNΣkQBCA

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.AnAΣkQBC

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 AP H A , entonces N E X P P / p o l y .ANEXPPSPACEAPHANEXPP/poly

Prueba Bosquejo: Supongamos que existe tal que P S P A C E AP H A . Si N E X P P / p o l y , entonces obtendríamos una contradicción.A N E X PANEXPPSPACEAPHANEXPP/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 .NEXPP/polyPSPACEPHNEXPP/polyPSPACE=PH

(vea aquí algunos detalles sobre los resultados conocidos de P / poly)

Michael Wehar
fuente
3
Probablemente valga la pena mencionar que se conjetura que PSPACE PH. es decir, un oráculo trivial funcionaría, pero simplemente no podemos probarlo.
Thomas apoya a Mónica el
1
¿Cómo, exactamente , define PSPACE relativizado? Más de una posibilidad aparece en la literatura. En particular, ¿se supone que las consultas de oráculo están polinomialmente delimitadas?
Emil Jeřábek apoya a Monica el
1
¿Incluye "La construcción de fórmulas Q", fórmulas booleanas grandes y monótonas que deciden los 2 ^ n qbfs de la fórmula original, en PH? Consulte Introducción a QSpace, Conferencia de satisfacción de 2002, Taller internacional sobre QBFS, para obtener más información sobre las fórmulas Q.
daniel pehoushek
1
Creo que puedo demostrar, como límite inferior, que tal ser A en SEH "tendría ramificaciones en la teoría de la complejidad estructural". ¿Debo publicar eso bastante pronto (lo que podría significar mañana o en 30 minutos), o dejar esto sin respuesta por más tiempo para que sea más probable que obtenga una respuesta con una clase que sea suficiente? A
1
Dado que los oráculos aleatorios tienen una alta complejidad de Kolmogorov, esperaría que cualquier límite superior computable en tales oráculos tenga consecuencias notables. Los límites superiores fuertes, como el exponencial simple, deberían tener fuertes consecuencias. (Por supuesto, este argumento es puramente heurístico y actualmente no tengo idea de cómo hacerlo riguroso).
András Salamon

Respuestas:

9

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))n2nf(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+nnm(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/(d1)>dpn(m(n))ndΣpdPHPHdnω(1)dsin 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)2n222n2

  • 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 ) .Npolylog(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=22n2polylog(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.n2nf(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 PP / p o l y ; oBPEXPP/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 PP / p o l y ; opolylog(N)poly(N)NPSVNEXPP/poly

  • ... para un algoritmo determinista, uno obtendría E X PP / p o l y .EXPP/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?).

Joshua Grochow
fuente
3
Un desafío que se pasa por alto aquí es que el oráculo que se construye tiene que ser un oráculo único y fijo, de modo que decidir que está en BPEXP o lo que sea. Si solo elige una semilla aleatoria de un buen generador, entonces, si bien obtiene un oráculo que funciona, no necesariamente obtiene un procedimiento de decisión para ese oráculo, ya que diferentes semillas dan (en general) diferentes oráculos. Tendría que hacer algo más, como encontrar una semilla canónica, para que la construcción sea realmente "constructiva".
Andrew Morgan
3
A pesar de que el argumento no le da a BPEXP, ¿puede reducir la complejidad a un nivel finito de EXPH?
Emil Jeřábek apoya a Monica el
2
@ EmilJeřábek: Sin verificar los detalles, creo que Σ 3 E X P debería funcionar. Adivina una semilla usando , verifica que funciona usando , y luego verifica que sea la semilla menos lexicográfica usando ¬ = ¬ , para un total de . Σ3EXP¬=¬
Joshua Grochow
2
@EmilJerabek: Por supuesto, si al menos pudiéramos reducir esto a M A E X P, eso sería aún mejor (no se puede mejorar sin probar nuevos límites inferiores del circuito), pero aún no veo cómo hacerlo ...
Joshua Grochow
2
@JoshuaGrochow Sí, tu publicación original parece estar bien. Estaba objetando su respuesta a Emil que suponía la hipótesis de que el oráculo se puede hacer en EXPH, donde el tiempo de ejecución es singularmente exponencial. En retrospectiva, debería haber sido más claro al respecto.
Andrew Morgan