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.

  • 3
    $\begingroup$ 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? $\endgroup$ May 23, 2014 at 23:38
  • 1
    $\begingroup$ 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). $\endgroup$
    – Kaveh
    May 24, 2014 at 10:06
  • $\begingroup$ 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. $\endgroup$
    – Lamine
    May 24, 2014 at 14:04
  • $\begingroup$ 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 $\endgroup$
    – vzn
    May 24, 2014 at 14:27
  • $\begingroup$ see also powerful algorithms too hard to implement, how can they be right $\endgroup$
    – vzn
    May 24, 2014 at 14:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.