Dauerhafte Fehler in der Informatik

Dies ist meine erste Frage auf dem Cstheory-Stapel, sei also nicht zu unhöflich, wenn ich irgendwie gegen die Etikette verstoße.

Wie wir wissen, machen in der Mathematik sogar berühmte Mathematiker, Superstars und Genies von Zeit zu Zeit schwere Fehler. Zum Beispiel liefern sowohl der 4-Farben-Satz als auch der Fermat-Satz dramatische Beispiele dafür, wie selbst klügste Köpfe getäuscht werden können. Es kann sogar Jahre dauern, um die Fehlerhaftigkeit einiger falscher Beweise zu beweisen.

Meine Frage ist: Können Sie herausragende Beispiele für solche Fehler in der Informatik nennen? Ich weiß nicht, so etwas wie "Dr. X hat 1972 bewiesen, dass es unmöglich ist, Y in weniger als 0 (log n) Zeit zu machen, aber 1995 stellte sich heraus, dass er tatsächlich falsch lag".

Ein berüchtigtes Beispiel für Computergeometrie ist der von Edelsbrunner, O'Rourke und Seidel veröffentlichte falsche Beweis des Zonensatzes für Hyperebenenanordnungen [FOCS 1983, SICOMP 1986]. Der Beweis erscheint auch in Edelsbrunners Lehrbuch zur rechnergestützten Geometrie von 1987.

Zonensatz: In jeder Anordnung von Hyperebenen in ist die Gesamtkomplexität aller Zellen, die eine Hyperebene schneiden, .R d O ( n d - 1$n$$\mathbb{R}^d$$O(n^{d-1})$

Der Zonensatz ist ein wichtiger Schritt, um zu beweisen, dass der standardmäßige rekursive Inkrementalalgorithmus zum Erstellen einer Anordnung von Hyperebenen in in läuft .R d O ( n d$n$$\mathbb{R}^d$$O(n^d)$

Raimund Seidel entdeckte 1990, dass der veröffentlichte Beweis falsch war, nachdem er von einem Studenten in seiner Klasse für rechnergestützte Geometrie in einem subtilen technischen Punkt in Frage gestellt worden war. Inzwischen eine riesige Literatur über Hyper / Halbraum / simplex / semialgebraische Bereich gesucht hatte entwickelt, die alle auf das verlassene Bauzeit für Vereinbarungen, die wiederum auf der Zone Satz verlassen. (Keiner dieser Autoren bemerkte den Fehler. Raimund hatte den veröffentlichten "Beweis" mehrere Jahre lang detailliert gelehrt, bevor er herausgefordert wurde.)$O(n^d)$

Glücklicherweise fanden Edelsbrunner, Seidel und Sharir fast sofort einen korrekten (und viel einfacheren!) Beweis für den Zonensatz [Neue Ergebnisse und neue Trends in CS 1991, SICOMP 1993].

Das Needham-Shroeder-Verschlüsselungsprotokoll mit öffentlichem Schlüssel, ein 5-Zeilen-Protokoll, wurde 17 Jahre nach seiner Veröffentlichung als unsicher eingestuft. Dies ist das beliebteste Beispiel von Verification-Mitarbeitern für die formale Analyse von Kryptoprotokollen.

Dick Lipton hat einen neuen Artikel über die Nicht-Monotonie des mathematischen Wissens veröffentlicht und dokumentiert darin Beispiele für Behauptungen, die sich als falsch herausgestellt haben oder zumindest korrigiert werden müssen.

Es hat Vermutungen gegeben, die sich als falsch erwiesen haben (z. B. die von Khot und Vishnoi widerlegte Einbettung von negativen Metriken durch konstante Verzerrung), aber es ist nichts Falsches daran, eine falsche Vermutung aufzustellen, schließlich handelt es sich um eine Vermutung.

Ein Beispiel für eine tatsächliche Verwirrung, die jedoch nicht lange anhielt, ist die parallele Wiederholung. Anfänglich wurde angenommen, dass für ein interaktives Protokoll mit einer Fehlerwahrscheinlichkeit der Fehler für k parallele Wiederholungen auf ϵ k reduziert wird . Diese Behauptung erwies sich als falsch, und Versuche, parallele Wiederholungen besser zu verstehen, ergaben sich als Türöffner für eine Menge schöner Mathematik.$\epsilon$$\epsilon^k$$k$

Es wird auch angenommen, dass Feynman es für offensichtlich hielt, dass (oder vielleicht, dass die Quantenmechanik von klassischen Computern offensichtlich nicht effizient simuliert werden kann). Aber dann war er weder ein theoretischer Informatiker, noch ist sich jemand der Richtigkeit dieser Geschichte sicher.$\mathsf{P} \neq \mathsf{NP}$

"Ich war schockiert, als ich erfuhr, dass das Binärsuchprogramm, das Bentley in Kapitel 5 von Programming Pearls als richtig erwiesen und anschließend getestet hat, einen Fehler enthält. Wenn ich Ihnen erst einmal sage, was es ist, werden Sie verstehen, warum es zwei Jahrzehnte lang der Erkennung entgangen ist. Damit Sie nicht glauben Ich wähle Bentley aus und möchte Ihnen sagen, wie ich den Fehler entdeckt habe: Die Version der binären Suche, die ich für das JDK geschrieben habe, enthielt denselben Fehler. Sie wurde Sun kürzlich gemeldet, als sie das Programm von jemandem brach, nachdem sie darauf gewartet hatte neun Jahre oder so. "

-

Joshua Bloch "Extra, Extra - Lesen Sie alles darüber: Fast alle binären Suchen und Zusammenführungen sind fehlerhaft" 2006