¿La diagonalización captura la esencia de la separación de clases?

11

No recuerdo haber visto una separación de clases no basada en resultados de diagonalización y relativización. La diagonalización aún podría usarse para separar las clases conocidas restantes, porque los argumentos no relativizantes aún podrían usarse en la conclusión de diagonalización, o en la construcción diagonalizada de la máquina de Turing. Aquí hay algunas preguntas relacionadas:

¿Existen pruebas de separación de clases no basadas en la diagonalización?

Y de ser así

¿Podemos encontrar un mecanismo de autorreferencia detrás de ellos?

Más lejos,

¿Cada separación de clase tiene una prueba "canónica natural" (en un sentido informal)?

Si es así, deberíamos tratar de encontrar argumentos no relativizantes, en lugar de otros esquemas de prueba para preguntas abiertas.

¿Se pueden reescribir todas las pruebas no diagonales en una diagonal?

Ludovic Patey
fuente
He editado la pregunta para intentar que sea más fácil de leer. Disculpas si he alterado tu intención.
András Salamon
@ András Gracias por tu edición. A menudo no estoy claro. Hay una alteración: quise decir que la diagonalización no falló porque dentro de ella, podemos usar argumentos no relativizantes. Creo que la relativización y la diagonalización son ortogonales. Y no considero que las pruebas que no usan diagonalización utilizarían un mecanismo de autorreferencia profundo, sino solo que, en una comprensión profunda de la prueba, podríamos descubrir un mecanismo de autorreferencia profundo ^^. Reeditaré esos puntos particulares.
Ludovic Patey

Respuestas:

15

Depende de cómo formalice la diagonalización. Kozen tiene un documento que muestra que cualquier separación de clase de complejidad debe ser una prueba de diagonalización.

Lance Fortnow
fuente
+1 Creo que leí esto en tu blog y estaba esperando tu respuesta :)
Mohammad Al-Turkistany
5

Como la diagonalización se relativiza, cualquier resultado de complejidad que implique relativizaciones contradictorias no puede basarse en la diagonalización. Citando a Arora-Barak :

Los resultados demostrados únicamente utilizando la diagonalización se relativizan en el sentido de que también son válidos para TM con acceso de oráculo a , para cada oráculo . Podemos usar esto para mostrar las limitaciones de tales métodos. En particular, los métodos relativizantes por sí solos no pueden resolver la pregunta P vs. NP.O { 0 , 1 } OO{0,1}

Una técnica importante de separación que no se relativiza es probar los límites inferiores del circuito. Por ejemplo, sabemos que todos los problemas en tienen circuitos polinómicos. Por otro lado, si demostramos que un problema de tiene un circuito superpolinomial (es decir, que muestra un límite inferior superpolinomial), entonces . Desafortunadamente, Razborov y Rudich mostraron que es poco probable que esta técnica resuelva el problema P vs. NP. (Ver prueba natural ). Un avance reciente en las separaciones de clases basado en probar los límites inferiores del circuito se discute en [1] y [2] .N P P N PPNPPNP

Otra técnica importante que no relativiza es la aritmetización. La técnica se usó primero para probar que ( Lund et al. ), Y luego para probar IP = PSPACE . Aaronson y Wigderson probaron que esta técnica era insuficiente para resolver P vs NP (denominada barrera de algebrización ).PPHIP

MS Dousti
fuente
2
Tenga en cuenta que Baker, Gill y Solovay no dijeron que la diagonalización no puede funcionar, pero hicieron una declaración más matizada "Parece poco probable que los métodos de diagonalización ordinarios sean adecuados".
András Salamon
@Sadeq No estoy de acuerdo en que la diagonalización se relativice. Por ejemplo, podría definir una máquina diagonal basada en una propiedad que tenga en cuenta la propiedad de localidad de cálculo, que no se relativiza.
Ludovic Patey
La algebrización no es una técnica, sino un concepto similar a la relativización. Supongo que te refieres a la aritmetización. ¿Y cuál es la conexión con las pruebas naturales?
Kristoffer Arnsfelt Hansen
1
@Sadeq: BGS claramente permitía una definición más inclusiva de diagonalización de lo que Arora-Barak parece tener la intención. Si un teórico conjunto como Robert Solovay piensa que podría haber otras nociones de diagonalización que no se relativizan, entonces quizás deberíamos dejar esa posibilidad abierta. Tenga en cuenta que la página 75 de A&B no descarta la posibilidad de que algún tipo de diagonalización utilice un hecho no relativizador sobre las máquinas Turing; el manuscrito aún no publicado de Arora-Impagliazzo-Vazirani indica que hay problemas bastante sutiles involucrados. cseweb.ucsd.edu/~russell/ias.ps
András Salamon
1
Existe cierto debate sobre esto: véase, por ejemplo, la respuesta de Fortnow al documento de AIV: people.cs.uchicago.edu/~fortnow/papers/relative.pdf
Suresh Venkat
5

Para agregar a la respuesta de Fortnow, continuando el trabajo de Kozen, Nash, Impagliazzo y Remmel formalizaron una noción de fuerte diagonalización y dieron algunas pruebas de que no se relativiza. Para responder parcialmente a su primera pregunta, sus resultados muestran que algunas pruebas de separación de clase no pueden basarse en una fuerte diagonalización. Aquí está el resumen:

Definimos y estudiamos la diagonalización fuerte y la comparamos con la diagonalización débil, implícita en [7]. El resultado de Kozen en [7] muestra que prácticamente todas las separaciones se pueden transformar en una diagonalización débil. Mostramos que hay clases de idiomas que no pueden separarse mediante una fuerte diagonalización y brindamos evidencia de que la diagonalización fuerte no se relativiza. También definimos dos tipos de diagonalización indirecta y estudiamos su poder.

Como definimos una fuerte diagonalización en términos de lenguajes universales, estudiamos su complejidad. Distinguimos y comparamos lenguajes universales débiles y estrictos. Finalmente, analizamos algunas variantes aparentemente más débiles de los lenguajes universales, que llamamos lenguajes pseudouniversales, y mostramos que, en condiciones de cierre débil, producen fácilmente lenguajes universales.

1-Nash, A., Impagliazzo, R., Remmel; J. "Lenguajes universales y el poder de la diagonalización". 18ª Conferencia Anual IEEE sobre Complejidad Computacional (CCC'03), p. 337, 2003.

Mohammad Al-Turkistany
fuente
5

¿Existen pruebas de separación de clases no basadas en la diagonalización?

Sí, hay, pero no para clases de complejidad uniforme. No tenemos un argumento para descartar tales pruebas, pero hasta ahora todas las separaciones entre clases de complejidad uniformes parecen utilizar la diagonalización en algún lugar.

¿Podemos encontrar un mecanismo de autorreferencia detrás de ellos?

No creo que las separaciones de clase de complejidad no uniforme se puedan convertir en argumentos de "autorreferencia" porque no son clases uniformes y no se pueden enumerar, y para un argumento de autorreferencia necesitamos enumerar los miembros de la clase.

¿Cada separación de clase tiene una prueba "canónica natural" (en un sentido informal)?

Depende de lo que quieras decir con "canónico". AFAIK, no hay consenso sobre las respuestas a la pregunta "¿Cuándo dos pruebas son idénticas en esencia?".

Si es así, deberíamos tratar de encontrar argumentos no relativizantes, en lugar de otros esquemas de prueba para preguntas abiertas. ¿Se pueden reescribir todas las pruebas no diagonales en una diagonal?

Como otros han señalado, la respuesta depende de lo que entiendas por diagonalización. En el sentido más general (documento de Kozen vinculado por Lance), la respuesta es sí para dos "clases de complejidad" diferentes (como se define en el documento de Kozen). Puede convertir el argumento en un argumento de "diagonalización". Pero:

  1. esto no se aplica a las clases de complejidad que no satisfacen los requisitos establecidos en el documento de Kozen (es decir, no son "clases de complejidad" de Kozen).
  2. Es un tipo de diagonalización muy general. Kozen muestra en el mismo documento que no hay "diagonalizaciones" que satisfagan algunas condiciones esperadas para separar las clases como y . Hay resultados de Lance Fornow y otros (por ejemplo, resultados de intercambio espacio-tiempo) (incluyendo algunos de los trabajos de Ryan William) donde la diagonalización se usa de manera indirecta. Esto puede convertirse en una "diagonalización" directa, pero no satisfará las buenas propiedades que uno podría esperar (como la independencia del contraejemplo para un conjunto en la clase más pequeña de los códigos de las máquinas para esa clase, y parece que esa es la razón no se relativizan)P S p a c ePPSpace
  3. lo importante es que cuanto más general es un método, más limitadas son sus aplicaciones (si se usa solo) porque el método debe funcionar para más casos y esto es una restricción en el método, no podemos usar el específico información que tenemos sobre el problema si no se comparte o no se puede reemplazar por algo similar para otros problemas a los que queremos aplicarles el método.
  4. Podemos convertir los argumentos de separación en argumentos de "diagonalización" (considerando la restricción que mencioné anteriormente), pero el hecho de que "la función de diagonalización realmente separa las clases" en sí misma necesita una prueba. El artículo de Kozen muestra que existe una función de diagonalización si las clases son diferentes, pero ¿cómo podemos saber que una función dada está realmente diagonalizando? ¡Necesitamos una prueba! Y el documento (AFAIU) no nos da ninguna idea sobre cómo presentar esas pruebas. Si tenemos un argumento de separación, podemos convertirlo en una prueba de diagonalización, pero eso es solo después deTener una prueba. La prueba original servirá como parte de la nueva prueba de diagonalización, mostrará que la función realmente está diagonalizando. (Y en cierto sentido, la prueba de diagonalización construida a partir del papel de Kozen no será "canónica" ya que dependerá completamente del argumento original).
Kaveh
fuente
Debería tener más cuidado con su segunda pregunta (¿Podemos encontrar un mecanismo de autorreferencia detrás de ellos?) Y la falta de uniformidad. Creo que debe ser más específico sobre lo que quiere decir con "un mecanismo de autorreferencia". La palabra "autorreferencia" es una de las palabras que se usa mucho (particularmente en obras filosóficas), por lo que debemos tener cuidado. El mecanismo habitual de autorreferencia (en el sentido de Godel, ver también el libro de R. Smullyan "Diagonalization and Self-Reference", 1994) necesita enumerar los objetos (aquí TM) de la clase más pequeña en el lenguaje. Pero hay otros que también usan
Kaveh
use la palabra "autorreferencia". EgK Mulmuley lo utiliza en la configuración no uniforme de su GCT en lo que él se refiere como la "paradoja de la autorreferencia". Pero es difícil ver para mí si eso es lo que tienes en mente cuando estás usando un "mecanismo de autorreferencia".
Kaveh