Errores duraderos en informática

Esta es mi primera pregunta sobre la pila de teoría, así que no seas demasiado grosero si estoy violando la etiqueta de alguna manera)

Como sabemos, en matemáticas incluso matemáticos famosos, superestrellas y genios están cometiendo serios errores de vez en cuando. Por ejemplo, tanto el teorema de 4 colores como el teorema de Fermat nos proporcionan casos dramáticos de cómo se pueden engañar incluso las mentes más brillantes. Incluso puede llevar años demostrar la incorrección de algunas pruebas falsas.

Mi pregunta es: ¿puede proporcionar algunos ejemplos destacados de tales errores en informática? No sé, algo así como "El Dr. X demostró en 1972 que es imposible hacer Y en menos tiempo que O (log n), pero en 1995 resultó que en realidad estaba equivocado".

Un ejemplo infame en geometría computacional es la prueba incorrecta del teorema de zona para arreglos de hiperplano publicado por Edelsbrunner, O'Rourke y Seidel [FOCS 1983, SICOMP 1986]. La prueba también aparece en el libro de texto de geometría computacional de 1987 de Edelsbrunner.

Teorema de zona: en cualquier disposición de hiperplanos en , la complejidad total de todas las celdas que intersecan cualquier hiperplano es .R d O ( n d - 1$n$$\mathbb{R}^d$$O(n^{d-1})$

El teorema de zona es un paso clave en la prueba de que el algoritmo incremental recursivo estándar para construir una disposición de hiperplanos en ejecuta en tiempo .R d O ( n d$n$$\mathbb{R}^d$$O(n^d)$

En 1990, Raimund Seidel descubrió que la prueba publicada era incorrecta, después de ser cuestionado en un punto técnico sutil por un estudiante en su clase de geometría computacional. Mientras tanto, se había desarrollado una gran literatura sobre la búsqueda de hiperplano / medio espacio / simplex / rango semialgebraico, todo lo cual dependía del tiempo de construcción para los arreglos, que a su vez se basaba en el Teorema de la Zona. (Ninguno de esos autores notó el error. Raimund había enseñado la "prueba" publicada en detalle durante varios años antes de ser cuestionado).$O(n^d)$

Afortunadamente, Edelsbrunner, Seidel y Sharir encontraron casi de inmediato una prueba correcta (¡y mucho más simple!) Del Teorema de la zona [Nuevos resultados y nuevas tendencias en CS 1991, SICOMP 1993].

El protocolo de criptografía de clave pública Needham-Shroeder, un protocolo de 5 líneas, se ha mostrado inseguro 17 años después de su publicación. Este es el ejemplo favorito de las personas de verificación para hacer análisis formales de protocolos criptográficos.

Dick Lipton tiene una nueva publicación sobre la no monotonicidad del conocimiento matemático, y en él documenta ejemplos de afirmaciones hechas que resultaron ser falsas, o al menos necesitadas de reparación.

Ha habido conjeturas que resultaron ser falsas (por ejemplo, incrustación de distorsión constante de métricas de tipo negativo refutadas por Khot y Vishnoi), pero no hay nada de malo en plantear una conjetura falsa ya que después de todo es una conjetura.

$\epsilon$$\epsilon^k$$k$

$\mathsf{P} \neq \mathsf{NP}$

"Me sorprendió saber que el programa de búsqueda binaria que Bentley demostró ser correcto y que posteriormente probó en el Capítulo 5 de Programming Pearls contiene un error. Una vez que le diga qué es, comprenderá por qué escapó a la detección durante dos décadas. Estoy molestando a Bentley, déjenme decirles cómo descubrí el error: la versión de búsqueda binaria que escribí para el JDK contenía el mismo error. Se informó a Sun recientemente cuando rompió el programa de alguien, después de esperar nueve años más o menos ".

-

Joshua Bloch "Extra, Extra - Lea todo sobre esto: casi todas las búsquedas binarias y Mergesorts están rotas" 2006