一千萬個為什麽

搜索

計算機科學中的長期錯誤

這是關於cstheory堆棧的第一個問題,所以如果我以某種方式違反禮儀,不要太粗魯)

眾所周知,在數學方面,即使是著名的數學家,超級巨星和天才也時不時會犯嚴重的錯誤。例如,4色定理和費馬定理為我們提供了一些戲劇性的案例,表明即使是最聰明的人也可以被欺騙。甚至可能需要數年才能證明某些證據的不正確性。

我的問題是 - 你能提供一些計算機科學中這類錯誤的傑出例子嗎?我不知道,像“X博士在1972年證明,在不到O(log n)時間內做Y是不可能的,但在1995年,事實證明他實際上是錯的”。

最佳答案

計算幾何中一個臭名昭著的例子是Edelsbrunner,O'Rourke和Seidel發表的超平面布置的區域定理的錯誤證明[FOCS 1983,SICOMP 1986]。證據也出現在Edelsbrunner 1987年的計算幾何教科書中。

區域定理:在$ \ mathbb {R} ^ d $中$ n $超平面的任何排列中,與任何超平面相交的所有單元格的總復雜度為$ O(n ^ {d- 1})$。

區域定理是證明在$ \ mathbb {R} ^ d $中構建$ n $超平面排列的標準遞歸增量算法在$ O(n ^ d)$時間內運行的關鍵步驟。

1990年,Raimund Seidel在一個學生在他的計算幾何課上被一個微妙的技術觀點挑戰後發現所發表的證據是不正確的。同時,開發了關於超平面/半空間/單面/半代數範圍搜索的巨大文獻,所有這些都依賴於$ O(n ^ d)$建設時間進行安排,而後者依賴於區域定理。 (這些作者都沒有註意到這個錯誤。在受到挑戰之前,Raimund已經詳細教授了已發表的“證據”。

幸運的是,Edelsbrunner,Seidel和Sharir幾乎立即找到了區域定理的正確(並且很多更簡單!)證明[1991年的新結果和新趨勢,SICOMP 1993]。

轉載註明原文: 計算機科學中的長期錯誤