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?
fuente
Respuestas:
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.
fuente
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 :
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 PP NP P≠NP
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 ).PPH⊆IP
fuente
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:
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.
fuente
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.
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.
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?".
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:
fuente