Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Are there any longstanding conjectures that ended ...

Expand Messages
  • GASARCH
    Mathematics and TCS are full of conjectures. Some are proven true, some are still not known. Most that have been resolved have been true: - Fermat s last
    Message 1 of 1 , Jun 8, 2009
    • 0 Attachment
      Mathematics and TCS are full of conjectures. Some are proven true, some are still not known. Most that have been resolved have been true:
      1. Fermat's last theorem should have been called a conjecture. It was proven. I don't think any serious mathematician ever thought it was false.
      2. Baudet's' Conjecture is now VDW's Theorem.
      3. The Modell Conjecture is now Faltings Theorem.
      4. I could list more, so could you.
      Are there any conjectures that ended up being false? Yes, though none listed below is really a clean story.
      1. Hilbert's 10th problem asked for an algorithm that would, given a poly in many variables over Z, determine if it has a Diophantine solution. We now know this cannot be done. While this may have surprised Hilbert, he was aware of this sort of thing happening. See the preface to his problems, or better see his entire address here.
      2. Same with the Ind of CH from ZFC. Hilbert thought it was true. More to the point, Hilbert certainly thought it had an answer. Now we know that it does not. Or at least that its ind of ZFC.
      3. NL=coNL surprised alot of people.
      4. In 1986 most people thought that P\ne BPP (hard to believe!). One notable exception was Mike Sipser. Now most people think that P=BPP. Of course, not resolved yet.
      I have not been able to find a dramatic example of a long standing conjecture that a large community believed ending up being false. Do you know of any?

      I doubt that any of the Clay problems will end up being false. I doubt that any serious mathematician thinks that any will end up being false. That might be self-correcting: if someone did we would label him (perhaps unfairly) non-serious.

      --
      Posted By GASARCH to Computational Complexity at 6/08/2009 10:54:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.