¿Las pruebas de que el permanente no está en uniforme relativizan?

Este es un seguimiento de esta pregunta y está relacionado con esta pregunta de Shiva Kinali.

Parece que las pruebas en estos documentos ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) usan teoremas de jerarquía. Quiero saber si las pruebas son teoremas de diagonalización " pura ", o si usan algo más que la diagonalización habitual. Entonces mi pregunta es

¿Existe una relativización razonable que ponga permanente en uniforme ? $\mathsf{TC^0}$

Tenga en cuenta que no estoy seguro de cómo definir el acceso a para uniform , sé que encontrar la definición correcta para clases de complejidad pequeña no es trivial. Otra posibilidad es que el permanente no esté completo para en el universo relativizado, en cuyo caso debería usar algún problema completo para en el universo relativizado en su lugar, y creo debería tener un problema completo en cualquier universo relativizado razonable. $\mathsf{TC^0}$ $\mathsf{\#P}$ $\mathsf{\#P}$ $\mathsf{\#P}$

cc.complexity-theory lower-bounds relativization permanent Kaveh
fuente

¿Cómo define una versión relativizada del permanente? ¿O estás buscando un mundo relativizado donde PP⊆TC ^ 0?

Tsuyoshi Ito

@ Tsuyoshi: El problema es que no estoy seguro de que la prueba de que el permanente se complete para . Me parece que la prueba de que el permanente no está en uniforme también funciona para cualquier otro problema completo. Una relativización razonable que ponga dentro de respondería a mi pregunta.

s h a r p P

$sharpP$

T C^{0}

$TC^0$

s h a r p P

$sharpP$

T C^{0}

$TC^0$

Kaveh

No estoy seguro de lo que quieres decir con relativización "razonable". Para cualquiera de las dos clases de complejidad, uno puede igualarlas tomando un oráculo lo suficientemente fuerte, ¿no? Por ejemplo, . (La primera clase es con "puertas QBF".)

A C 0^{P S P A C E} = P S P A C E = P S P A C E^{P S P A C E}

$AC0^{PSPACE} = PSPACE = PSPACE^{PSPACE}$

A C 0

$AC0$

Ryan Williams

@ Ryan: pensé que la forma en que uno define el acceso al oráculo es importante, y si la definición no es correcta, pueden suceder cosas extrañas. Por ejemplo, vea esto cs.toronto.edu/~sacook/homepage/rel-web.ps . (nota: no recordaba que también hablaran de ) Una máquina con más recursos puede hacer preguntas más complicadas que una más restringida del mismo oráculo y esa es la razón por la que no tenemos un (razonable ) relativización que haría que DTime (n) = DTime ( ), por lo que me parece que no es tan sencillo como usted dice, ¿verdad?

T C^{0}

$TC^0$

n^{2}

$n^2$

Kaveh

A C^{0} = L H

$AC^0 = LH$ (jerarquía de tiempo de registro) , por lo que no debería haber una relativización razonable que haría que

. Siento que probablemente algo está mal con mi razonamiento en la línea anterior, ¿sabemos

\subset P H \subseteq P S p a c e

$\subset PH \subseteq PSpace$

A C^{0} = P S p a c e

$AC^0 = PSpace$

L H \subset P H

$LH \subset PH$

Kaveh

Respuestas:

Cualquier separación de clases cerrada bajo "recursos polinomiales" tiene un oráculo que los hace iguales. (Esto se proporciona si el mecanismo del oráculo es justo y permite que ambos modelos de máquina realicen consultas de longitud polinómica y nada más).

Deje que sea " con puertas para el oráculo ". Dejando que sea un lenguaje completo de bajo reducciones de , tenemos , donde en el mecanismo del oráculo para $TC0^{O}$ $TC0$ $O$ $O$ $PSPACE$ $TC0$ $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$ , contamos el uso del espacio de la cinta Oracle junto con el resto de la memoria. (Por lo tanto, solo se realizan consultas de longitud polinómica). Tal igualdad es válida para muchas clases "cerradas bajo recursos polinómicos", en el sentido de que pueden hacer consultas de longitud polinómica a un oráculo, pero no más grandes. Estas clases incluyen cosas como , , (bajo un mecanismo de oráculo diferente que no cuenta las consultas de oráculo hacia el espacio), , , y $PSPACE$ $AC0$ $TC0$ $LOGSPACE$ $P$ $NP$ $PH$ . Por lo tanto, cualquier separación de clases en esta lista necesariamente debe usar algún tipo de argumento "no relativizante". Esto también implica (por ejemplo) que las pruebas naturales de cosas como Paridad que no están en no son relativizantes (pero esto es aún más fácil: todo lo que necesitas aquí es un oráculo para la paridad, por lo que obtienes ) $PP$ $AC0$ $AC0[2]$

En la colección de pruebas que cita, creo que la mayoría de ellas (si no todas) funcionan asumiendo y derivando una contradicción. Este tipo de resultados se denominan "diagonalización indirecta". Por lo que una relativización de su prueba tendría que decir: "si , entonces la contradicción ...", pero esta suposición es realmente cierto para algunos oráculos . $TC0 = PP$ $TC0^{O} = PP^{O}$ $O$

En los comentarios, se señaló que en la forma en que lo estoy usando. Estas son solo sutilezas con el mecanismo del oráculo. En el lado de LOGSPACE, la cinta de consulta no puede ser parte del límite de espacio, ya que las consultas tienen una longitud polinómica. En el lado de PSPACE, la cinta de consulta es $LOGSPACE^{O} = PSPACE^{O}$ tomado como parte del espacio limitado. Eso fue para hacer las cosas "justas". Pero si les das exactamente el mismo mecanismo de oráculo, de hecho, puedes separarlos nuevamente por diagonalización. Por ejemplo, si las consultas no cuentan para el espacio limitado, entonces en PSPACE ^ {PSPACE} puede hacer preguntas exponencialmente largas a PSPACE, por lo que de hecho esto contiene EXPSPACE. Pido disculpas por no decir esto explícitamente antes.

El cálculo limitado por el espacio es muy sutil con respecto a los oráculos. Consulte la página 5 de este artículo de Fortnow para obtener un buen resumen de por qué el cálculo de Oracle y el espacio no siempre se mezclan.

Ryan Williams
fuente

Gracias por el comentario sobre PSPACE ^ {PSPACE} que contiene EXPSPACE en el modelo que utilizamos para LOGSPACE. Mi confusión ha sido aclarada.

Robin Kothari

Ver también Aehlig, Cook y Nguyen, Relativizing clases de pequeña complejidad y sus teorías .

Yuval Filmus