Долгосрочные ошибки в информатике

Это мой первый вопрос о стеке теории, так что не будь слишком груб, если я как-то нарушаю этикет)

Как известно, в математике даже известные математики, суперзвезды и гении время от времени совершают серьезные ошибки. Например, и теорема о 4 цветах, и теорема Ферма дают нам драматические случаи того, как даже самые яркие умы могут быть обмануты. Даже могут потребоваться годы, чтобы доказать ошибочность некоторых ложных доказательств.

Мой вопрос - можете ли вы привести некоторые выдающиеся примеры таких ошибок в информатике? Я не знаю, что-то вроде «Доктор Х доказал в 1972 году, что невозможно сделать Y меньше, чем за O (log n) времени, но в 1995 году оказалось, что он на самом деле был неправ».

Печально известным примером в вычислительной геометрии является неверное доказательство теоремы о зоне для гиперплоскостных схем, опубликованное Эдельсбруннером, О'Рурком и Зайделем [FOCS 1983, SICOMP 1986]. Доказательство также содержится в учебнике по вычислительной геометрии Эдельсбруннера 1987 года.

Теорема о зоне. При любом расположении гиперплоскостей в общая сложность всех ячеек, пересекающих любую гиперплоскость, равна .R d O ( n d - 1$n$$\mathbb{R}^d$$O(n^{d-1})$

Теорема о зоне является ключевым шагом в доказательстве того, что стандартный рекурсивный инкрементный алгоритм для построения расположения гиперплоскостей в выполняется за время.R d O ( n d$n$$\mathbb{R}^d$$O(n^d)$

В 1990 году Раймунд Зайдель обнаружил, что опубликованное доказательство было неверным, после того, как студент из его класса вычислительной геометрии оспаривал тонкую техническую точку зрения. Тем временем была разработана огромная литература по поиску гиперплоскости / полупространства / симплекса / полуалгебраического диапазона, все из которых основывались на времени построения для аранжировок, что, в свою очередь, основывалось на теореме о зоне. (Ни один из этих авторов не заметил ошибку. Раймунд подробно учил опубликованное «доказательство» в течение нескольких лет, прежде чем его оспаривали.)$O(n^d)$

К счастью, Эдельсбруннер, Зайдель и Шарир почти сразу нашли правильное (и намного проще!) Доказательство теоремы о зоне [Новые результаты и новые тенденции в CS 1991, SICOMP 1993].

Криптографический протокол с открытым ключом Needham-Shroeder, состоящий из 5 строк, оказался небезопасным через 17 лет после его публикации. Это любимый пример проверяющих людей для формального анализа крипто-протоколов.

У Дика Липтона есть новый пост о немонотонности математических знаний, и в нем он документирует примеры заявлений, которые оказались ложными или, по крайней мере, нуждались в исправлении.

Были гипотезы, которые оказались ложными (например, вложение с постоянным искажением метрик отрицательного типа, опровергнутых Хотом и Вишным), но нет ничего плохого в том, чтобы выдвигать ложную гипотезу, поскольку в конце концов это гипотеза.

Примером реальной путаницы, которая длилась недолго, является параллельное повторение. Первоначально считалось, что для интерактивного протокола с вероятностью ошибки ошибка уменьшается до для параллельных повторений. Это утверждение оказалось ложным, и на самом деле попытки лучше понять параллельное повторение оказались открытием для большого количества прекрасной математики.ϵ к$\epsilon$$\epsilon^k$$k$

Также считается, что Фейнман считал очевидным, что (или, может быть, квантовая механика, очевидно, не может быть эффективно смоделирована классическими компьютерами). Но тогда он не был теоретиком компьютерных наук, и никто не уверен в точности этой истории.$\mathsf{P} \neq \mathsf{NP}$

«Я был шокирован, узнав, что программа бинарного поиска, которую Bentley доказал, что она была правильной и впоследствии протестирована в главе 5« Программирование жемчуга », содержит ошибку. Как только я скажу вам, что это такое, вы поймете, почему она избежала обнаружения в течение двух десятилетий. Я выбираю Bentley, позвольте мне рассказать вам, как я обнаружил ошибку: Версия бинарного поиска, которую я написал для JDK, содержала ту же ошибку. Об этом недавно было сообщено Sun, когда она ломала чью-то программу, после ожидания девять лет или около того. "

-

Джошуа Блох "Extra, Extra - Читать все об этом: почти все бинарные поиски и слияния нарушены" 2006