Potentes algoritmos que son demasiado difíciles de implementar: ¿cómo asegurarse de que son correctos?

9

Me refiero a la pregunta aquí: algoritmos poderosos demasiado complejos para implementar .

Si un algoritmo es poderoso, pero demasiado complejo para implementar, ¿cómo puede estar seguro de que el algoritmo es correcto? Sin la implementación, no podrá probar el algoritmo en un escenario del mundo real, y un algoritmo tan complejo puede contener errores, lo que puede invalidar el algoritmo.

Esto es lo que no entiendo; Si tiene las técnicas para demostrar la exactitud de un algoritmo, entonces ya tendría el algoritmo para implementarlo, ¿no es así? O bien, ¿cómo podemos estar seguros de que la técnica de prueba es correcta?

Lo siento si sueno elemental!

Actualización de Kaveh (¡reproducida aquí porque el argumento es mejor!):

Si puede probar formalmente la exactitud de un algoritmo en un sistema formal como Coq, entonces también puede extraer el algoritmo (porque esencialmente ha implementado el algoritmo), pero el hecho clave es que para la mayoría de los algoritmos no damos pruebas formales de corrección del algoritmo, utilizamos pruebas informales de corrección. Las pruebas pueden ser falsas, lo que sucede de vez en cuando, e incluso una prueba formal de corrección no nos hará estar absolutamente seguros de que el algoritmo es correcto.

ds.algorithms implementation Graviton
fuente
66
Es por eso que tenemos técnicas para probar la corrección de los algoritmos, incluso si la implementación (correcta) en una máquina real es difícil.
Raphael
99
Estoy de acuerdo con Raphael. Parece que la pregunta se basa en el supuesto de que la corrección de un algoritmo generalmente se prueba al implementarlo, pero no es el caso. Probar la exactitud de un algoritmo e implementar un algoritmo son cosas completamente diferentes, y una cosa no implica la otra en ninguna dirección.
Tsuyoshi Ito
8
Algoritmos simples con pruebas complejas de corrección: ¿cómo sabe que tienen razón? El hecho de que un algoritmo funcione en ejemplos de prueba no significa que funcione en todas las entradas.
Peter Shor
2
Estoy de acuerdo con la mayoría de los comentarios, pero creo que les falta un punto clave. Si puede probar formalmente la exactitud de un algoritmo en un sistema formal como Coq, entonces también puede extraer el algoritmo (porque esencialmente ha implementado el algoritmo), pero el hecho clave es que para la mayoría de los algoritmos no damos pruebas formales de corrección del algoritmo, utilizamos pruebas informales de corrección. Las pruebas pueden ser falsas, eso sucede de vez en cuando, e incluso una prueba formal de corrección no nos hará estar absolutamente seguros de que el algoritmo es correcto.
Kaveh
55
"Tenga cuidado con los errores en el código anterior; solo he demostrado que es correcto, no lo he probado". ~ Donald Knuth
Lev Reyzin

Respuestas:

11

Hace varios años, ha habido un debate (bastante duro) sobre un tema similar a este. Todo comenzó cuando varias pruebas complejas resultaron ser incorrectas, y algunos investigadores comenzaron a plantear dudas sobre la naturaleza misma de las pruebas (bueno, debería haber dicho "criptografía comprobable", pero en aras de la generalidad, no lo hice) . Ambos lados de la controversia acusaron al otro de entender mal los conceptos. Aquí hay un enlace para más información .

Las pruebas son nuestras herramientas (matemáticas) para demostrar que los teoremas / algoritmos son correctos, pero cuando se vuelven demasiado complejos, podemos deslizarnos y demostrar que las cosas incorrectas son correctas. La reciente prueba de más o menos 100 páginas en P ≠ NP es un excelente ejemplo. Sin embargo, esto no descarta la naturaleza misma de las pruebas: no hay nada malo en ellas.

Un último punto: creo que estudiar la filosofía de la ciencia nos dará más información sobre esto. (Bajo el enlace dado, vea la viñeta " ¿Cómo sabemos si una prueba matemática es correcta? ")

MS Dousti
fuente