Erros duradouros na ciência da computação

Esta é minha primeira pergunta na pilha de histórias, portanto, não seja muito rude se eu estiver violando a etiqueta de alguma forma)

Como sabemos, em matemática, mesmo matemáticos, astros e gênios famosos estão cometendo erros sérios de tempos em tempos. Por exemplo, o teorema de quatro cores e o teorema de Fermat nos fornecem casos dramáticos de como até as mentes mais brilhantes podem ser iludidas. Pode levar anos até para provar a incorreção de algumas provas falsas.

Minha pergunta é: você pode fornecer alguns exemplos notáveis ​​de tais erros na ciência da computação? Não sei, algo como "Dr. X provou em 1972 que é impossível fazer Y em menos de O (log n) tempo, mas em 1995 descobriu-se que ele estava realmente errado".

Um exemplo infame da geometria computacional é a prova incorreta do Teorema da Zona para arranjos de hiperplanos publicados por Edelsbrunner, O'Rourke e Seidel [FOCS 1983, SICOMP 1986]. A prova também aparece no livro de geometria computacional de Edelsbrunner, de 1987.

Teorema da Zona: Em qualquer arranjo de hiperplanos em R d , a complexidade total de todas as células que cruzam qualquer hiperplano é O ( n d - 1 ) .$n$$\mathbb{R}^d$$O(n^{d-1})$

A Zona Teorema é um passo chave na prova de que o algoritmo recursivo periódica padrão para construir um arranjo de hiperplanos em R d é executado em S ( n d ) tempo.$n$$\mathbb{R}^d$$O(n^d)$

Em 1990, Raimund Seidel descobriu que a prova publicada estava incorreta, depois de ser desafiada em um ponto técnico sutil por um aluno em sua aula de geometria computacional. Enquanto isso, uma enorme literatura sobre busca de hiperplano / meio espaço / simplex / semialgebraica havia sido desenvolvida, todas baseadas no tempo de construção de para arranjos, que por sua vez se baseavam no Teorema da Zona. (Nenhum desses autores notou o bug. Raimund ensinou a "prova" publicada em detalhes por vários anos antes de ser desafiado.)$O(n^d)$

Felizmente, Edelsbrunner, Seidel e Sharir encontraram quase imediatamente uma prova correta (e muito mais simples!) Do Teorema da Zona [Novos Resultados e Novas Tendências em CS 1991, SICOMP 1993].

O protocolo de criptografia de chave pública Needham-Shroeder, um protocolo de 5 linhas, mostrou-se inseguro 17 anos após a sua publicação. Este é o exemplo favorito das pessoas da Verificação para fazer uma análise formal dos protocolos de criptografia.

Dick Lipton publicou um novo post sobre a não monotonicidade do conhecimento matemático e nele documenta exemplos de afirmações feitas que se revelaram falsas ou, pelo menos, necessárias, de correção.

Houve conjecturas que se mostraram falsas (por exemplo, incorporação de distorção constante de métricas de tipo negativo refutadas por Khot e Vishnoi), mas não há nada de errado em apresentar uma falsa conjectura, pois, afinal, é uma conjectura.

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

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

"Fiquei chocado ao saber que o programa de pesquisa binária que a Bentley se mostrou correto e posteriormente testado no Capítulo 5 do Programming Pearls contém um bug. Depois que eu lhe disser o que é, você entenderá por que escapou da detecção por duas décadas. Estou usando Bentley, deixe-me contar como descobri o bug: a versão da pesquisa binária que escrevi para o JDK continha o mesmo bug.Também foi relatado à Sun recentemente quando interrompeu o programa de alguém, depois de esperar por nove anos mais ou menos. "

-

Joshua Bloch "Extra, Extra - Leia tudo sobre isso: quase todas as pesquisas e mergesorts binários estão quebrados" 2006