La siguiente pregunta utiliza ideas de criptografía aplicadas a la teoría de la complejidad. Dicho esto, es una pregunta puramente teórica de la complejidad, y no se requiere ningún conocimiento criptográfico para responderla.
Deliberadamente escribo esta pregunta de manera informal. A falta de detalles, posiblemente se indique un poco incorrectamente. No dude en señalar las correcciones en sus respuestas.
En el siguiente documento:
Criptografía no maleable, Danny Dolev, Cynthia Dwork y Moni Naor, SIAM Rev. 45, 727 (2003), DOI: 10.1137 / S0036144503429856 ,
los autores escriben:
Supongamos que el investigador A ha obtenido una prueba de que P ≠ NP y desea comunicar este hecho al profesor B. Suponga que, para protegerse, A prueba su afirmación de B de una manera de conocimiento cero ...
Hay varios problemas estándar de NP completo, como la satisfacibilidad (SAT), Graph-Hamiltonicity y Graph-3-Colorability (G3C), para los cuales existen pruebas de conocimiento cero. La forma estándar de probar cualquier teorema de NP es reducirlo primero a una instancia de los problemas de NP completos antes mencionados, y luego realizar la prueba de conocimiento cero.
Esta pregunta se refiere a tal reducción. Suponga que la P vs. NP se liquida de cualquiera de las siguientes maneras:
- P = NP
- P ≠ NP
- P vs. NP es independiente de la teoría de conjuntos axiomáticos estándar.
Deje σ denotar la prueba. Entonces, P vs. NP está en un lenguaje NP (ya que existe una breve prueba de ello). La reducción del teorema (digamos, P ≠ NP) al problema NP-completo (digamos SAT) es independiente de σ. Es decir:
There exists a formula ϕ which is satisfiable if and only if P ≠ NP.
¡Esto está más allá de mi imaginación! Parece que, incluso si se nos da la prueba σ, es poco probable que podamos construir tal fórmula ϕ.
¿Alguien podría arrojar algo de luz sobre esto?
Además, dejemos que L sea un lenguaje NP en el que se encuentra P vs. NP . El lenguaje consiste en infinitos teoremas como P vs. NP , de tamaños arbitrarios.
¿Qué es un candidato para L?
¿Puede L ser NP-completo?
Respuestas:
La forma de ver la prueba de un enunciado matemático (por ejemplo, una resolución de P vs NP) como una pregunta de la forma "es fórmula ... satisfactoria" es la siguiente:
Arreglar algún sistema de axioma. Dada una cadena de longitud n, si la cadena es una prueba de la declaración matemática en el sistema axiomático, es algo que se puede definir de manera directa: la cadena debe consistir en proposiciones. Cada proposición debe ser un axioma o debe seguir a partir de las proposiciones anteriores por una de las reglas de inferencia.
No es un problema definir una fórmula booleana que verifique todo esto. ¡Todo lo que debe saber es la longitud n de la prueba!
fuente
Eso no tiene mucho sentido para mí. NP es una clase de complejidad para problemas de decisión que tienen instancias arbitrariamente grandes, y P vs. NP no los tiene. Por lo que dices después:
en su lugar, puede significar que P vs. NP es una instancia de un problema de NP; pero por supuesto que lo es! También es una instancia de un número infinito de problemas P, DTIME (n), etc. En particular, aquí hay dos candidatos DTIME (1) para L, uno de los cuales es correcto: siempre devuelve
true; o siempre vuelvofalse.fuente