Ejemplo de un algoritmo que carece de una prueba de corrección

18

Tenemos la lógica de Hoare. ¿Por qué todavía es posible que un algoritmo sea correcto pero no hay pruebas de que sea correcto? Supongamos que el algoritmo se expresa en C. Luego, podemos argumentar paso a paso que está haciendo lo que se supone que debe hacer.

Entonces mi pregunta es:

Dame un ejemplo de un algoritmo correcto pero que no tenga una prueba de corrección.

EDITAR: Creo que un poco de información puede ayudar a aclarar a dónde voy. Déjame citar a Scott Aaronson:

Desde la década de 1970, se especula que P NP podría ser independiente (es decir, ni demostrable ni refutable) de los sistemas de axiomas estándar para las matemáticas, como la teoría de conjuntos de Zermelo-Fraenkel. Para ser claros, esto significaría que $\ne$

no existe un algoritmo de tiempo polinómico para problemas de NP completo, pero nunca podemos probarlo (al menos no en nuestros sistemas formales habituales), o de lo contrario

un algoritmo de tiempo polinómico para problemas NP-completos hace existir, pero tampoco nunca puede probar que funciona, o que nunca se puede demostrar que se detiene en tiempo polinómico.

Me refiero a la segunda posibilidad. Dado que Aaronson puede enumerarlo tan confiadamente como una posibilidad, creo que debe haber un ejemplo existente del tipo 2. Es por eso que estoy haciendo esta pregunta. Pero parece que no se ve una respuesta rápida y clara.

correctness-proof hoare-logic Zirui Wang
fuente

17

¿Qué significa decir que un algoritmo es correcto si no tenemos una prueba de corrección?

David Richerby

14

¿Quiere decir "la prueba de corrección es imposible" o "nadie demostró que es correcta"?

gnasher729

12

Los algoritmos no tienen que ser correctos ... suponga que tiene esto: (1) coloque un cubo vacío en el alféizar de la ventana por la mañana. (2) bájalo por la noche. (3) mida el volumen de agua en el balde. (4) repita a la mañana siguiente. Esta es una descripción de un algoritmo, pero no describe nada que pueda llamarse "correcto" sin un estiramiento. Curiosamente, la mayoría del código de programación en el mundo está escrito de esta manera en particular: simplemente no le preocupa la corrección de lo que hace.

wvxvw

@wvxvw Estoy confundido entonces, ¿qué significa que un algoritmo sea "correcto"? Si hace lo que estaba destinado a hacer, ¿no significa eso que es correcto? Si el objetivo de su escenario fuera encontrar la cantidad promedio de agua recolectada en el balde durante la lluvia, para cada día, ¿no sería correcto el algoritmo en ese caso?

Abdul

8

@chi no entiendes ... no es que a los programadores no les importe la corrección de su código, es que para algunos algoritmos el concepto de "corrección" no es aplicable. Tome alguna aplicación .NET WindowsForms, que dice algo al respecto: "coloque este botón con esta etiqueta en esta posición, luego coloque este otro botón en esta otra posición y así sucesivamente ..." - puede haber alguna interpretación de lo que esto el programa lo hace, en virtud del cual lo que hace puede juzgarse como (in) correcto (por ejemplo, el diseñador gráfico dice que "se ve feo"), pero eso es todo lo posible.

wvxvw

50

Aquí hay un algoritmo para la función de identidad:

Entrada: $n$
Compruebe si el º cadena binaria codifica una prueba de en ZFC, y si es así, la salida $n$ $0 > 1$ $n+1$
De lo contrario, salida $n$

La mayoría de las personas sospechan que este algoritmo calcula la función de identidad, pero no lo sabemos, y no podemos probarlo en el marco comúnmente aceptado para las matemáticas, ZFC .

Yuval Filmus
fuente

2

¿Está seguro de comprobar si el º cadena binaria codifica una prueba de en ZFC $n$ $0 > 1$ es un algoritmo?

Dmitry Grigoryev

23

No, pero la verificación definitivamente se puede implementar algorítmicamente (es decir, mediante una máquina Turing). De hecho, este es uno de los requisitos que tenemos para los sistemas de prueba: que la validez de la prueba se pueda verificar algorítmicamente.

Yuval Filmus

66

@Puppy ZFC prueba

. Pero también podría probar

si (f) es inconsistente. Casi todos creen que ZFC es consistente, por supuesto, pero debido a los teoremas de incompletitud no podemos saberlo con certeza.

\neg (0 > 1)

$\lnot (0>1)$

0 > 1

$0>1$

chi

1

@Nathaniel Para nada. Puede probar fácilmente la exactitud de cada algoritmo de libro de texto, por ejemplo. Este algoritmo difiere en que se basa en la consistencia de ZFC, que es algo que ZFC por sí mismo no puede probar.

Yuval Filmus

1

@Nathaniel: Si lo desea, continuemos esta discusión en el chat .

user21820

9

La mayoría de los algoritmos no han demostrado ser correctos en la lógica de Hoare. La razón principal es que tales pruebas de corrección son extremadamente caras a partir de enero de 2017, probablemente en varios órdenes de magnitud en comparación con la 'mera' programación. Hay mucho trabajo en curso para reducir este costo mediante la automatización, pero es una lucha cuesta arriba.

Otra razón por la cual un algoritmo podría no tener una prueba de corrección, y una que es más relevante en la práctica que los fenómenos de incompletitud que mencionaron Yuval y Chi, es que podríamos no saber cuál es esta especificación. Este problema tiene dos dimensiones.

Los clientes no saben lo que quieren. Este es un problema bien conocido en ingeniería de software, y los ingenieros de software han desarrollado muchos enfoques para lidiar con esto.
La especificación es difícil. Un buen ejemplo es la corrección de los algoritmos criptográficos. Recientemente, Micali & Goldwasser ganó los premios Turing por especificar qué significa seguridad criptográfica. Sin embargo, tenga en cuenta que esa definición es (hasta donde yo sé) para "criptografía teórica" donde tiene un parámetro de seguridad $n$ que van más allá de los números naturales, y los adversarios son máquinas de Turing probabilísticas de tiempo polinomial. A mi leal saber y entender (corríjame si me equivoco), existe un desajuste entre la teoría y la práctica, y los algoritmos concretos como AES y SHA256 no están dentro del alcance de esas especificaciones teóricas. No creo que haya una especificación completa para tales algoritmos, por lo tanto, no podemos, en principio, verificarlos en el sentido de, por ejemplo, la lógica de Hoare.

Martin Berger
fuente

AES está dentro del alcance de las definiciones de seguridad criptográfica. (Debe usar definiciones de seguridad concretas en lugar de definiciones asintóticas, pero debe hacerlo de todos modos si desea seguridad en la práctica).

DW

@DW Interesante. No estaba al tanto de esto. ¿Cómo se evita la naturaleza asintótica de la criptografía teórica? ¿Me puede señalar un artículo sobre esto? ¿Qué pasa con las funciones hash criptográficas concretas?

Martin Berger el

en.wikipedia.org/wiki/Concrete_security , y las referencias enumeradas allí. Las funciones hash son un caso más complejo, porque depende de para qué las use, pero las complejidades son en gran medida ortogonales a la seguridad asintótica frente a la seguridad concreta.

DW

2

Para el cifrado, necesita dos algoritmos: uno que cifra, otro que descifra. Uno de ellos no puede ser correcto por sí solo. Solo pueden ser correctos en un par (usted prueba que descifrar una entrada cifrada produce el original). Pero para el cifrado, desea que sea indescifrable y eso es algo que no puede captar con "exactitud".

gnasher729

1

@DW Tengo que estar en desacuerdo un poco. Si bien los documentos de Rogaway y Bellare son geniales, implican que de alguna manera permiten pruebas de seguridad de los primitivos es engañoso. Ambos documentos tratan esencialmente de protocolos (es decir, suponen que primitivas como AES, SHA, RSA, etc.) son seguras y luego prueban las cosas desde allí. El problema esencial de demostrar que las primitivas son seguras permanece. Si tiene alguna referencia para pruebas de que las primitivas son seguras, me interesaría. El segundo documento, por ejemplo, supone que RSA es difícil, lo cual es un problema abierto.

DRF

5

Esto está ligado a lo incompleto de la lógica subyacente. De hecho, la lógica de Hoare generalmente contiene una regla debilitada o "pre-post" donde las implicaciones

\frac{P ⟹ P^{'} {P^{'}} c {Q^{'}} Q^{'} ⟹ Q^{'}}{{P} c {Q}}

$\dfrac{ P \implies P' \qquad \{P'\}c\{Q'\} \qquad Q' \implies Q' }{ \{P\}c\{Q\} }$

necesita ser probado en una lógica subyacente, generalmente lógica de primer orden (FOL) con alguna axiomatización teórica de conjuntos como Zermelo-Fraenkel (ZF).

P ⟹ P^{'}, Q ⟹ Q^{'}

$P\implies P', Q\implies Q'$

$P(n)$ $P(0)$ $P(1)$ $P(2)$ $\forall n\in \mathbb{N}.\ P(n)$

$M$ $n$ $P(n)$ $M$ $\forall n.\ P(n)$ $M$ $\forall n.\ P(n)$

chi
fuente

5

Problema: Escriba "Sí" si cada número par ≥ 4 es la suma de dos primos, y "No" si hay un número par ≥ 4 que no es la suma de dos primos.

Algoritmo: Imprimir "Sí"

La mayoría de la gente piensa que el algoritmo es correcto. No hay ninguna prueba conocida, y es muy posible que no es ninguna prueba.

gnasher729
fuente

3

Cualquier algoritmo que sea correcto pero no sabemos cuánto tiempo tarda en ejecutarse puede transformarse en un algoritmo que se detiene en un período de tiempo garantizado, pero no estamos seguros de si es correcto.

Por ejemplo, para encontrar un primo mayor que $n$ , comienza a contar desde $n+1$ probando si cada número es primo hasta que encuentre uno. Ahora modifíquelo para darse por vencido y regresar $0$ si no podemos encontrar una prima después $\log(n)^2$ intentos. Si el algoritmo modificado alguna vez regresa $0$ , es incorrecto, pero nadie sabe si eso sucede o no. Incluso con tantos como $\sqrt{n}$ siempre se encontrarán pasos que no podamos probar como primos.

Entonces, tenemos un algoritmo que es correcto pero no tenemos pruebas de que se ejecute en tiempo polinómico, y un algoritmo (el mismo, pero limitado en el tiempo) que se ejecuta en tiempo polinómico pero no tenemos pruebas de que sea correcto. Y como con el $P=NP$ problema, para este ejemplo también es plausible que no existan tales pruebas.

Dan Brumleve
fuente

Ejemplo de un algoritmo que carece de una prueba de corrección

Respuestas: