[Computational Complexity] Are there any longstanding conjectures that ended ...
- 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 theorem should have been called a conjecture. It was proven. I don't think any serious mathematician ever thought it was false.
- Baudet's' Conjecture is now VDW's Theorem.
- The Modell Conjecture is now Faltings Theorem.
- I could list more, so could you.
- 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.
- 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.
- NL=coNL surprised alot of people.
- 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 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