Computación Aleatoria e Interactiva
Permitir que los algoritmos lancen monedas o entablen un diálogo con un probador potente pero no confiable produce clases de complejidad como BPP e IP que reconfiguran nuestra comprensión de lo que la verificación eficiente puede lograr.
Definition
La computación aleatoria aumenta una máquina con acceso a bits aleatorios y mide la probabilidad de una respuesta correcta, mientras que la computación interactiva permite que un verificador de tiempo polinomial intercambie mensajes con un probador; las clases resultantes capturan problemas resolubles con error acotado o verificables a través de la interacción.
Scope
Este tema cubre las clases de complejidad probabilística, incluyendo BPP, RP y ZPP, y la cuestión de si la aleatoriedad puede eliminarse, los sistemas de prueba interactivos y el teorema que identifica IP con PSPACE, las pruebas de conocimiento cero y las pruebas verificables probabilísticamente que subyacen a la dificultad de la aproximación.
Core questions
- ¿El acceso a la aleatoriedad permite que los algoritmos resuelvan más problemas de manera eficiente?
- ¿Puede un verificador limitado comprobar las afirmaciones hechas por un probador potente y no confiable?
- ¿Cómo se puede convencer a alguien de que una afirmación es verdadera sin aprender nada más?
- ¿Cómo restringe la verificación de pruebas interactiva y probabilística la aproximación?
Key theories
- IP es igual a PSPACE
- Los lenguajes demostrables mediante un protocolo interactivo entre un verificador de tiempo polinomial y un probador todopoderoso son exactamente aquellos decidibles en espacio polinomial, una medida sorprendente del poder de la interacción.
- El teorema PCP
- Todo problema en NP tiene pruebas que pueden verificarse leyendo solo un número constante de bits elegidos aleatoriamente, un resultado que establece el umbral preciso más allá del cual la aproximación de muchos problemas de optimización es NP-difícil.
Clinical relevance
Estas ideas tienen un impacto tecnológico directo: las pruebas de conocimiento cero permiten protocolos de autenticación y preservación de la privacidad y sustentan la computación verificable en las cadenas de bloques, mientras que las pruebas verificables probabilísticamente explican por qué muchos problemas de optimización no pueden aproximarse eficientemente, guiando dónde los algoritmos de aproximación pueden y no pueden tener éxito.
History
Las pruebas interactivas y de conocimiento cero fueron introducidas por Goldwasser, Micali y Rackoff y por Babai a mediados de la década de 1980. Shamir demostró que IP es igual a PSPACE en 1990, y el teorema PCP, completado por Arora y otros a principios de la década de 1990, revolucionó el estudio de la aproximación, mientras que la conjetura de que el tiempo polinomial aleatorio es igual al tiempo polinomial determinista sigue abierta.
Debates
- ¿La aleatoriedad añade un poder computacional genuino?
- Muchos resultados sugieren que BPP es igual a P bajo suposiciones de dificultad plausibles, lo que significa que la aleatoriedad podría, en principio, eliminarse de los algoritmos eficientes. Si esta desaleatorización se mantiene incondicionalmente es una cuestión sin resolver, dejando abierta la pregunta de cuán esencial es realmente la aleatoriedad.
Key figures
- Shafi Goldwasser
- Silvio Micali
- László Babai
- Adi Shamir
Related topics
Seminal works
- aroraBarak2009
- goldreich2008
Frequently asked questions
- ¿Cómo puede el lanzamiento de monedas ayudar a un algoritmo?
- La aleatoriedad permite que un algoritmo evite entradas en el peor de los casos al tomar decisiones que el adversario no puede predecir, lo que a menudo produce procedimientos más simples o rápidos, como en las pruebas de primalidad. La clase BPP de error acotado captura los problemas resolubles de esta manera con una pequeña y controlable probabilidad de error.
- ¿Qué es una prueba de conocimiento cero?
- Es un protocolo interactivo que convence a un verificador de que una afirmación es verdadera sin revelar nada más allá de su veracidad, ni siquiera por qué se cumple. Dichas pruebas permiten, por ejemplo, demostrar que se conoce una contraseña o un secreto sin revelarlo, y son fundamentales para la privacidad criptográfica moderna.