Respuesta aceptada
La respuesta de Scott Aaronson ha sido "aceptada" (¡principalmente porque es la única respuesta!)
Resumen de respuesta de una oración Las generalizaciones plausiblemente naturales de la pregunta P versus NP no son obviamente más fáciles de resolver que P versus NP en sí.
Una obstrucción a una respuesta general La pregunta original suponía que cada clase de complejidad A se asocia "naturalmente" a una generalización no determinista NA; sin embargo, una clase de complejidad general A se puede definir de tantas maneras que el mapa de clase N A NA no puede (aparentemente) recibir fácilmente una especificación completamente general y manifiestamente natural.
Sin embargo ... el comentario de dkuper (a continuación ) proporciona un enlace a una charla de Christos Kapoutsis (LIAFA), titulada Minicomplexity , que describe una estrategia de investigación en la línea indicada.
Para una discusión más profunda, un recurso recomendado es la Carta perdida de Dick Lipton / Ken Regan Gödel y el ensayo P = NP titulado Creemos mucho, pero podemos demostrar poco.
La pregunta finalmente hecha
La pregunta ¿Qué rasgo compartido por cada clase de complejidad A ⊂ P que es más rica que NTIME (n ln n), actúa para obstruir las pruebas de A ⊂ NA?
Esta pregunta fue motivada por los comentarios recientes del blog de Scott Aaronson (ver más abajo), y la riqueza teórica de la complejidad de esta pregunta ha sido posteriormente iluminada por comentarios / respuestas / ensayos de Robin Kathari , Scott Aaronson , Ryan Williams , Dick Lipton y Ken Regan , y preguntas anteriores de TCS StackExchange .
Observaciones (1) Para todas las clases de complejidad conocidas A ⊂ P que son lo suficientemente grandes como para incluir NTIME (n ln n) ⊂ A, el problema A NA está abierto, y (2) la razón (s) para esta obstrucción teórica de la complejidad casi universal no se entiende actualmente bien.
Al igual que muchas personas, siempre había apreciado la inmensa dificultad de probar P ⊂ NP, pero no había apreciado previamente que probar A ⊂ NA es un problema abierto para (esencialmente) todas las clases de complejidad computacional.
La pregunta originalmente formulada
En su weblog Shtetl Optimized , Scott Aaronson emitió el siguiente desafío TCS :
El desafío Shtetl Optimized TCS Si cree que P vs. NP es indecidible, debe responder:
La pregunta Shtetl Optimized TCS ¿Por qué cualquier intuición le dice que [ P vs NP es indecidible ] no también le dice que las preguntas P versus EXP, NL versus PSPACE, MAEXP versus P / poly, TC0 versus AC0 y NEXP versus ACC son similares indecidible?
(En caso de que no lo sepa, esos son cinco pares de clases de complejidad que han demostrado ser diferentes entre sí, a veces utilizando ideas muy sofisticadas).
Se aceptarán respuestas a la siguiente pregunta específica:
Q1 (pregunta de literatura de TCS) ¿Alguna clase de complejidad conocida A y B satisface de manera comprobable A ⊂ B y NA ⊇ B, para NA la extensión natural no determinista de A?
Suponiendo que la respuesta a Q1 es "sí", se desea una explicación de cómo sucede que se ha probado la inclusión estricta A ⊂ B, mientras que la inclusión estricta (superficialmente similar) P ⊂ NP es difícil de probar.
Alternativamente, si la respuesta a Q1 es "no", se hace una pregunta más:
P2 ( La pregunta TCS optimizada de Shtetl extendida ) ¿Las inclusiones de clase de complejidad de la forma general A ⊂ B y NA ⊇ B son demostrables, en ZFC o cualquier extensión finita de ZFC, para cualquier clase de complejidad "natural"? (si "sí" construye ejemplos; si "no" prueba la obstrucción).
El agradecimiento y las gracias de PostScript se extienden a TCS StackExchange por mantener esta comunidad matemática maravillosamente inspiradora y útil, y a Scott Aaronson por mantener su admirable weblog Shtetl Optimized.
fuente
Respuestas:
John, aunque agradecemos tus amables comentarios, confieso que no entiendo cómo se relaciona tu pregunta con el simple punto que hice en el comentario citado. Todo lo que dije fue que sí conocemos varias separaciones entre clases de complejidad, como P ≠ EXP, MA EXP ⊄P / poly, NEXP⊄ACC, etc. Entonces, si cree que una separación particular, como P ≠ NP, es " demasiado profundo para ser probado o refutado en la teoría de conjuntos ZF "(o lo que sea), entonces me parece que la carga recae sobre usted para explicar por qué cree que la separación tiene que ser independiente de ZF, mientras que otras separaciones resultaron no ser ser. Para que este argumento tenga fuerza, no veo la necesidad de que las otras separaciones tengan la forma particular que especificó.
Pero de todos modos para responder a su pregunta: bueno, ¡el desafío obvio al responder es encontrar cualquier clase de complejidad A para la que podamos probar que A está estrictamente contenido en NA, donde NA es "la extensión natural no determinista de A"! (De hecho, como Robin señala anteriormente, encontrar una A es equivalente a responder su pregunta tal como la ha formulado). Y los únicos ejemplos de tales A que se me ocurren son cosas como el TIEMPO (f (n)) ( se demostró en la década de 1970 que TIME (f (n)) ≠ NTIME (f (n)) para f (n) ≤n log * n, ya que NTIME (f (n)) puede simular un tiempo ligeramente mayor que f (n )). (Una versión anterior de esta publicación afirmaba que era conocida por todosf (n). ¡Gracias a Ryan Williams por la corrección!) Por lo tanto, configurar A = TIME (n) y B = NTIME (n) respondería su pregunta afirmativamente. Un ejemplo más "natural" probablemente tendrá que esperar un avance en la teoría de la complejidad.
[Nota: deseo aclarar que no le puse nombres portentosos como "The Shtetl Optimized this or that" --- ¡esas fueron las elaboraciones de Sidles!]
fuente