<p>I am asking the following: which of the 'famous' computer science results have been thoroughly checked, and for which ones is the correctness still uncertain?</p>

<p>I understand that some proofs are hard to check due to their length, intricacy or technicality, and in some cases an elementary proof was found after the first published one (such as Dinur's proof of the PCP theorem). Apparently, some of the longest proofs in CS are the SPGT by Chudnovsky et al., and the Graph Minors series of papers by Robertson-Seymour, and I understand that there is an ongoing effort to simplify the latter.</p>

<p>The same question applies to mathematics where there are some very long proofs, such as the CFSG, which correctness is debated by experts: see <a href="http://en.wikipedia.org/wiki/List_of_long_proofs" rel="nofollow">List of long proofs</a>.</p>

CC BY-SA 3.0
2014-05-23T23:38:29.287Z
I'm not sure I understand the question. Do you want to know about the status of the theorems you mentioned, like the PCP theorem, graph minors theorem, SPGT and CFSG, or do you want examples of theorems whose correctness is uncertain? And what is your threshold for uncertainty? For example, are the graph minors theorem and the classification of finite simple groups certain in your opinion or is their correctness debated?
Robin Kothari
CC BY-SA 3.0
2014-05-24T10:06:17.470Z
I haven't seen or heard anything like what you describe. Please give one or two examples of major published results in TCS whose correctness is debated among experts in the topic (and give the names of those who debate them with references).
Kaveh
CC BY-SA 3.0
2014-05-24T14:04:24.957Z
My advisor doubts the proof of the 4 color theorem because of the use of computer verification. I don't know if this doubt is shared by some graph theory experts.
Lamine
CC BY-SA 3.0
2014-05-24T14:27:44.820Z
this a sort of meta-topic of CS but rarely discussed directly that does relate to eg proof verification topics and also it is known that some proofs are later found to have glitches and/or revised. its similar to the topic of defects in software. some are minor, some are major. even knuth (with his implementation/practitioner focus) recently said in interview he doubts or does not trust some large complex algorithms devised for problems, eg many are never implemented and/or tested. see eg MO [widely accepted proofs later found wrong](http://mathoverflow.net/questions/35468/)
vzn
CC BY-SA 3.0
2014-05-24T14:33:12.473Z
see also [powerful algorithms too hard to implement, how can they be right](http://cstheory.stackexchange.com/questions/4512/powerful-algorithms-that-are-just-too-hard-to-implement-how-to-be-sure-they-ar)
vzn
CC BY-SA 3.0
2014-05-24T14:33:49.457Z
also [long lasting errors in CS](http://cstheory.stackexchange.com/questions/7753/long-lasting-errors-in-computer-science)
vzn
CC BY-SA 3.0
2014-05-24T14:47:07.667Z
this is a recent case of a [revision/correction of the Vazirani-Micali](http://rjlipton.wordpress.com/2014/03/28/a-matchless-result/) algorithm for graph matching.
vzn
CC BY-SA 3.0
2014-05-24T14:50:54.817Z
another interesting case study is this controversial paper in Notices AMS by Koblitz [uneasy relationship between math/crypto](http://www.ams.org/notices/200708/tx070800972p.pdf) but was subj to much later [pushback](http://www.ams.org/notices/200711/tx071101454p.pdf) by top researchers.
vzn
<proofs>
Famous computer science results which correctness is uncertain?
Stephan Krilow
# Famous computer science results which correctness is uncertain?

(Asked by: username_0 on 2014-05-23)

I am asking the following: which of the 'famous' computer science results have been thoroughly checked, and for which ones is the correctness still uncertain?

I understand that some proofs are hard to check due to their length, intricacy or technicality, and in some cases an elementary proof was found after the first published one (such as Dinur's proof of the PCP theorem). Apparently, some of the longest proofs in CS are the SPGT by Chudnovsky et al., and the Graph Minors series of papers by Robertson-Seymour, and I understand that there is an ongoing effort to simplify the latter.

The same question applies to mathematics where there are some very long proofs, such as the CFSG, which correctness is debated by experts: see [List of long proofs](http://en.wikipedia.org/wiki/List_of_long_proofs).

**Tags:** proofs

> **Comments:**
> **username_1**: I'm not sure I understand the question. Do you want to know about the status of the theorems you mentioned, like the PCP theorem, graph minors theorem, SPGT and CFSG, or do you want examples of theorems whose correctness is uncertain? And what is your threshold for uncertainty? For example, are the graph minors theorem and the classification of finite simple groups certain in your opinion or is their correctness debated?  
> **username_2**: I haven't seen or heard anything like what you describe. Please give one or two examples of major published results in TCS whose correctness is debated among experts in the topic (and give the names of those who debate them with references).  
> **username_3**: My advisor doubts the proof of the 4 color theorem because of the use of computer verification. I don't know if this doubt is shared by some graph theory experts.  
> **username_4**: this a sort of meta-topic of CS but rarely discussed directly that does relate to eg proof verification topics and also it is known that some proofs are later found to have glitches and/or revised. its similar to the topic of defects in software. some are minor, some are major. even knuth (with his implementation/practitioner focus) recently said in interview he doubts or does not trust some large complex algorithms devised for problems, eg many are never implemented and/or tested. see eg MO [widely accepted proofs later found wrong](http://mathoverflow.net/questions/35468/)  
> **username_4**: see also [powerful algorithms too hard to implement, how can they be right](http://cstheory.stackexchange.com/questions/4512/powerful-algorithms-that-are-just-too-hard-to-implement-how-to-be-sure-they-ar)  
> **username_4**: also [long lasting errors in CS](http://cstheory.stackexchange.com/questions/7753/long-lasting-errors-in-computer-science)  
> **username_4**: this is a recent case of a [revision/correction of the Vazirani-Micali](http://rjlipton.wordpress.com/2014/03/28/a-matchless-result/) algorithm for graph matching.  
> **username_4**: another interesting case study is this controversial paper in Notices AMS by Koblitz [uneasy relationship between math/crypto](http://www.ams.org/notices/200708/tx070800972p.pdf) but was subj to much later [pushback](http://www.ams.org/notices/200711/tx071101454p.pdf) by top researchers.  

---

## 0 answers

