Las Pruebas son las bases para todas las matemáticas. Una prueba es un reclamo o teorema que estás intentando demostrar una secuencia de derivaciones realizadas para declarar que el teorema ha sido demostrado. Ej. Todos los ángulos de un triángulo total de 180° pueden ser comprobados independientemente por cualquiera (verificador).
Pruebas
Probador —> Hace el reclamo —> Verificador elige —> Acepta/Rechaza
(Ambos, el probador y el verificador, son algoritmos)
En informática los términos para prueba eficientemente verificables es Prueba NP. Estas pruebas cortas pueden ser verificables en tiempo polinomial. La idea general es “Existe una solución para un teorema y es pasado al verificador para comprobarlo”
https://github.com/ZecHub/zechub/assets/27905787/e8089f44-bd9a-4056-82df-19af0a880a01
En un lenguaje-NP = dos condiciones se deben cumplir:
Integridad: los reclamos auténticos serán aceptados por el verificador (permite a los probadores honestos alcanzar la verificación)
Solidez: los reclamos falsos no tendrán pruebas (para todas las estrategias tramposas, el probador tramposo será incapaz de probar la correctitud del reclamo incorrecto).
Interacción: en lugar de solo leer la prueba, el verificador se compromete con un probador de varias rondas de mensajes.
Aleatoriedad: las solicitudes del verificador al probador son aleatorias y el probador debe ser capaz de responder correctamente a cada uno.
https://github.com/ZecHub/zechub/assets/27905787/af082a5d-583e-4b10-99c2-39dff196ab11
Usando interacción y aleatoriedad juntas, es posible probar un reclamo para un verificador a ciegas en Tiempo Probabilístico Polinómico [Probabilistic Polynomial Time (PPT)].