¿Es ALogTime! = PH difícil de probar (y desconocido)?

Lance Fortnow afirmó recientemente que probar L! = NP debería ser más fácil que probar P! = NP :

Separar NP del espacio logarítmico. Di cuatro enfoques en una encuesta previa al blog de 2001 sobre la diagonalización (Sección 3), aunque ninguno ha funcionado. Debería ser mucho más fácil que separar P de NP.

La Sección 3 de la encuesta vinculada afirma que no hay resultados significativos de colapso del oráculo:

Mientras que la pregunta P! = NP sigue siendo bastante formidable, la pregunta L! = NP parece mucho más manejable. No tenemos motivos para pensar que esta pregunta sea difícil. La falta de buenos modelos de relativización para el espacio significa que no tenemos un modelo de oráculo significativo donde L y NP colapsan. Además, dado que L es una clase uniforme, no se aplican las limitaciones de Razborov-Rudich [RR97].

Una pregunta sobre las barreras de relativización conocidas para L! = NP en este sitio recibió una respuesta que señalaba que el problema TQBF completo de PSPACE se puede usar como oráculo para obtener tal colapso. Una objeción sobre si este fue un modelo de oráculo significativo parece ser respondida también.

Pero incluso si entendiera por qué "no tenemos un modelo de oráculo significativo en el que el colapso de L y NP" deba considerarse como una afirmación correcta, todavía tendría mis dudas sobre si probar L! = NP es más factible que probar P! = NOTARIO PÚBLICO. Si probar L! = NP debería ser realmente más fácil que probar P! = NP, entonces probar ALogTime! = PH definitivamente debería estar al alcance. (El artículo de la encuesta sugiere la posibilidad de separar de ) Supongo que ALogTime! = PH todavía está abierto, y me gustaría saber si hay buenas razones para esperar que sea difícil de probar. $\Sigma_2^p$ $L$

cc.complexity-theory reductions relativization Thomas Klimpel
fuente

Lance Fortnow 7:03 AM, 13 de mayo de 2016 : "Permítanme reformular mi punto. Deje que AP sea un polimetro alterno (se sabe que PSPACE no está relativizado y, por lo tanto, es diferente de L). Entonces no hay un modelo de relativización conocido que haga que L = NP para algún oráculo pero separa L de AP para todos los oráculos ".

Thomas Klimpel

Respuestas:

No estoy seguro de por qué Fortnow dice que "no hay un modelo significativo donde y colapsen" ... me parece que QBF debería hacerlos colapsar, según el modelo habitual de oráculo Ruzzo-Simon-Tompa (y el enlace que incluyó está de acuerdo). Tenga en cuenta que este modelo de oráculo también tiene sus peculiaridades: tenemos si y solo si para cada oráculo $L$ $NP$ $L = NL$ $L^A = NL^A$ $A$ , por lo que cualquier oráculo que presencia una separación implicaría la separación no relativizada.

$NC1$ $ALogTime = NP$ $NC1$ $NP$ $NC1$ bajo esa noción. Consulte el Teorema 6 en http://link.springer.com/article/10.1007/BF01692056 . (Una advertencia: técnicamente hablando, ese documento considera LOGSPACE-uniform NC1, pero creo que alguna versión razonable de esa construcción de oráculo debería funcionar en el entorno LOGTIME-uniform).

Más allá de eso, no conozco ninguna razón particular para creer que sea "difícil de probar", aparte de la observación de que muchas personas lo han intentado y ninguna ha tenido éxito todavía.

Ryan Williams
fuente

L = N L

$L = NL$

L^{A} = N L^{A}

$L^A = NL^A$

A

$A$

L

$L$

Creo que hay una prueba de la declaración en el documento que vinculé. Con respecto a su segunda oración: ¿pregunta por qué Fortnow dice que Razborov-Rudich no se aplica? Si es así, su punto es que la barrera de las pruebas naturales, como se entiende comúnmente, solo se aplica si el modelo con el que se limita no es uniforme, por ejemplo, P / poli.

Ryan Williams

Ah, leí mal: pensé que la barrera que no se aplicaba era la relativización, no pruebas naturales, lo siento. Lo que quise preguntar fue: ¿por qué la relativización es una barrera para P vs NP pero no L vs NL, moralmente? (De ahí la falta de relación de la pregunta.)

Michaël Cadilhac

En resumen, es porque el modelo RST Oracle no le permite realizar pasos no deterministas a menos que la cinta Oracle esté en blanco. (Las razones son sutiles; básicamente algunos resultados no se relativizarán sin él.) El argumento real es más complicado ...

Ryan Williams

Una idea ingenua para probar ALogTime! = PH: El problema del valor de la fórmula booleana es completo para ALogTime bajo reducciones de tiempo de registro deterministas . Por lo tanto, si ALogTime = PH, entonces PH = coNP = ALogTime y, por lo tanto, el problema del valor de la fórmula booleana se completaría con reducciones de tiempo de registro deterministas para coNP. Por lo tanto, habría una reducción determinista del tiempo de registro del problema de tautología al problema del valor de la fórmula booleana.

Las reducciones de tiempo de registro deterministas deben ser inofensivas, no pueden contribuir mucho a la solución del problema de tautología. Son solo una buena formalización de lo que significa que una reducción solo puede funcionar muy localmente. Por lo tanto, la tarea restante es comprender por qué el problema de la tautología no puede convertirse en un problema de valor de fórmula booleana mediante reducciones muy locales. Todavía no veo cómo hacerlo, pero al menos la tarea restante es muy clara, por lo que tengo al menos la oportunidad de entender por qué es difícil (o no).

Thomas Klimpel
fuente