Długotrwałe błędy w informatyce

To jest moje pierwsze pytanie na stosie cstheory, więc nie bądź zbyt niegrzeczny, jeśli w jakiś sposób naruszam etykietę)

Jak wiemy, w matematyce nawet znani matematycy, supergwiazdy i geniusze od czasu do czasu popełniają poważne błędy. Na przykład, zarówno twierdzenie 4-kolorowe, jak i twierdzenie Fermata dostarczają nam dramatycznych przypadków, w których nawet najmądrzejsze umysły mogą zostać zwiedzione. Potwierdzenie nieprawidłowości niektórych dowodów fałszowania może zająć nawet lata.

Moje pytanie brzmi - czy możesz podać wybitne przykłady takich błędów w informatyce? Nie wiem, coś w rodzaju „Dr X udowodnił w 1972 r., Że niemożliwe jest wykonanie Y w czasie krótszym niż O (log n), ale w 1995 r. Okazało się, że tak naprawdę się mylił”.

Niesławnym przykładem geometrii obliczeniowej jest niepoprawny dowód twierdzenia o strefie dla układów hiperpłaszczyzn opublikowanego przez Edelsbrunner, O'Rourke i Seidel [FOCS 1983, SICOMP 1986]. Dowód pojawia się również w podręczniku geometrii obliczeniowej Edelsbrunnera z 1987 roku.

Twierdzenie o strefie: w dowolnym układzie hiperpłaszczyzn w całkowita złożoność wszystkich komórek przecinających jakąkolwiek hiperpłaszczyznę wynosi .$n$$\mathbb{R}^d$$O(n^{d-1})$

Twierdzenie o strefie jest kluczowym krokiem w dowodzie, że standardowy rekurencyjny algorytm inkrementalny do budowy układu hiperpłaszczyzn w działa w czasie .$n$$\mathbb{R}^d$$O(n^d)$

W 1990 roku Raimund Seidel odkrył, że opublikowany dowód jest niepoprawny, po tym, jak uczeń podważył go w swojej subtelnej kwestii technicznej w swojej klasie geometrii obliczeniowej. W międzyczasie opracowano ogromną literaturę dotyczącą przeszukiwania hiperpłaszczyzny / półprzestrzeni / simpleksu / semialgebraicznego, z których wszystkie opierały się na czasie budowy dla układów, który z kolei opierał się na twierdzeniu o strefie. (Żaden z tych autorów nie zauważył błędu. Raimund nauczył szczegółowo opublikowanego „dowodu” przez kilka lat, zanim został zakwestionowany.)$O(n^d)$

Na szczęście Edelsbrunner, Seidel i Sharir prawie natychmiast znaleźli poprawny (i znacznie prostszy!) Dowód twierdzenia o strefie [Nowe wyniki i nowe trendy w CS 1991, SICOMP 1993].

Protokół kryptografii klucza publicznego Needham-Shroeder, 5-liniowy, okazał się niepewny 17 lat po jego opublikowaniu. Jest to ulubiony przykład osób weryfikujących przeprowadzanie formalnej analizy protokołów kryptograficznych.

Dick Lipton opublikował nowy post na temat niemonotoniczności wiedzy matematycznej, w którym dokumentuje przykłady twierdzeń, które okazały się fałszywe lub przynajmniej wymagały naprawy.

Istnieją przypuszczenia, które okazały się fałszywe (np. Osadzanie stałego zniekształcenia metryk typu negatywnego obalonego przez Khota i Vishnoi), ale nie ma nic złego w przedstawianiu fałszywej domniemania, ponieważ w końcu jest to domniemanie.

Przykładem zamieszania, które nie trwało długo, jest równoległe powtarzanie. Początkowo sądzono, że w przypadku protokołu interaktywnego z prawdopodobieństwem błędu , błąd zmniejsza się do dla równoległych powtórzeń. Twierdzenie to okazało się fałszywe, a w rzeczywistości próby lepszego zrozumienia równoległych powtórzeń okazały się otwarte na wiele pięknych matematyki.ϵ k$\epsilon$$\epsilon^k$$k$

Uważa się również, że Feynman uważał za oczywiste, że (a może mechanika kwantowa oczywiście nie może być skutecznie symulowana przez klasyczne komputery). Ale nie był on teoretycznym informatykiem ani nikt nie jest pewien dokładności tej historii.$\mathsf{P} \neq \mathsf{NP}$

„Byłem zszokowany, gdy dowiedziałem się, że program do wyszukiwania binarnego, który Bentley okazał się poprawny, a następnie przetestowany w rozdziale 5 Programowania pereł, zawiera błąd. Gdy powiem ci, co to jest, zrozumiesz, dlaczego uniknął wykrycia przez dwie dekady. Wybieram Bentleya, powiem wam, jak odkryłem błąd: wersja wyszukiwania binarnego, którą napisałem dla JDK, zawierała ten sam błąd. Niedawno został zgłoszony firmie Sun, gdy złamał program, po tym, jak czekał na około dziewięciu lat. ”

-

Joshua Bloch „Extra, Extra - Przeczytaj wszystko na ten temat: Prawie wszystkie wyszukiwania binarne i Mergesorts są zepsute” 2006