Demostrar la Hipótesis de Riemann sin revelar otra cosa que se demostró

Question

Considere la siguiente afirmación de Scott Aaronson del blog:

Suponiendo que probar la de Riemann Hipótesis, es posible convencer a alguien de ese hecho, sin revelando otra cosa que el hecho de que lo demostró. También es posible para escribir la prueba hacia abajo de tal manera que alguien pudo verificar, con la confianza muy alta, teniendo solamente visto 10 o 20 bits de la prueba.

¿Alguien puede explicar de dónde este resultado proviene de?

Answer 1

La respuesta correcta ya ha sido dada por Akhil Mathew en los comentarios de arriba.

El tema pertenece al campo de la teoría de la complejidad en ciencias de la computación. En la teoría de la complejidad, existe un interesante concepto para el problema de decidir si una palabra pertenece a un determinado lenguaje formal o no: interactivo de los sistemas de prueba. Estos sistemas modelo de la interacción entre los recursos limitados verificador (es decir, a usted o a mí) y que el todopoderoso armario (dice, mucho, mucho más inteligente hermana mayor). El objetivo de la interacción es que el armario de la convence de que el verificador del hecho de que la palabra dada es o no es un elemento de la lengua, tal que:

• casi seguramente, el verfier sólo puede ser convencido de la verdadera respuesta y
• el verificador sólo puede ser engañado para creer que el opuesto dentro de un margen muy pequeño de error.

Hay un gran número de resultados teóricos con respecto a estos sistemas interactivos. Estos resuts incluyen las siguientes dos declaraciones (dado informalmente):

• todo lo que puede ser probado por un interactiva protocoll también puede ser probada mediante un sistema interactivo de protocoll que la convence de que el verificador (dentro de un pequeño margen de error), pero no revelan ninguna información sobre la prueba en sí. (Cero-Conocimiento-a Prueba de, "Todo lo comprobable es comprobable en conocimiento cero" por parte de Ben-O et al, 1988)
• cada prueba puede ser reescrito tal de que la inspección de sólo un número constante de bits de esta prueba convence el verificador dentro de sólo un pequeño margen de error (PCP-Theorem, la "Prueba de la verificación y la dureza de aproximación a los problemas" por Arora et al, 1992), y un número de otros documentos)

Ambos de estos conceptos y los resultados son altamente no trivial y más allá del alcance de este foro.

Por supuesto, en la cita anterior Scott Aaronson es sólo el uso de algunos cotidiana del problema para ilustrar estos conceptos. El uso de estos resultados formalmente, se habría de convertir la tarea de "probar la Hipótesis de Riemann" para un problema de decisión de los lenguajes formales, como es norma en la teoría de la complejidad.

---

EDIT: de hecho Hay una pequeña modificación en el modelo entre ambos resultados se indicó anteriormente que omití. En primer lugar, la interacción entre un armario y el verificador puede ser generalizado a varias provers y un verificador. Después, hay un resultado que se considera que el caso de múltiples provers puede ser equivalentemente, reformulada de la siguiente manera: El provers se quitan el protocolo, sino que hay una sola (posiblemente muy largo) de una cadena que actúa como una prueba escrita de la palabra problema. La interacción se está buscando un elegido de forma arbitraria poco de esta prueba, y el verificador podrá elegir la ubicación de estos bits de forma aleatoria. Esto se llama un Probabilístico Seleccionable Prueba (por lo tanto, PCP). Así ,en este escenario, la "prueba escrita" de la Hipótesis de Riemann sería interpretado como la cadena de prueba.

Answer 2

El punto es que SHORTPROOF es NP-completo problema: dada una frase de longitud $n$, en el lenguaje de algunos formal de la prueba del sistema (ZFC, la aritmética de Peano, etc), no se tiene una prueba de longitud en la mayoría de los fijos polinomio en $n$,$(2n)^{100}$? Es en NP, porque para un razonable sistema formal puede comprobar una determinada prueba con bastante rapidez. Este problema fue considerado en Goedel carta de von Neumann que, implícitamente, declaró lo que ahora llamamos el $P \neq NP$ pregunta (el corazón del problema, la universalidad de hormigón del tipo NP-completo los problemas, no era conocido hasta mucho más tarde).

Cualquier NP-completos problema tiene un cero-prueba de conocimiento de protocolo para la demostración de las soluciones de los casos, por ejemplo, que tenemos un SHORTPROOF de la hipótesis de Riemann. Estas son las "pruebas que revelan otra cosa que su propia validez".

El papel de la PCP es el teorema a demostrar que la prueba protocolos (interactivo de desafío/respuesta de juegos) puede ser muy eficaz para cualquier nivel estipulado de confianza. La probabilidad de que el demostrador realmente tiene un SHORTPROOF de Riemann, dado que se sigue el protocolo y el armario de gana, es al menos el 99 por ciento, o lo que sea especificado grado de certeza.

Answer 3

El concepto detrás de esto es prueba de conocimiento Cero. Wikipedia tiene un buen artículo sobre esto.

La cuestión similar se hizo en papel "Cómo Demostrar un Teorema de Modo que nadie Puede Reclamar Que" por M. Blum. También este artículo aborda la cuestión.