[Computational Complexity] The Mystique of the Open Problem
- The story goes that Andrew Wiles dreamt of proving Fermat's last theorem when he was a kid. No surprise since all of us math-loving kids dreamed of solving this famous problem. We certainly talked about it much longer than the more important Fermat's Little Theorem which already had a proof. Now my kids have never heard of Fermat's last theorem. Why should they? Nothing there left to dream there.It is the challenges that inspire. It was much more interesting to go to the moon in the 60's than it is today. Computational complexity is blessed with such a great challenge, one of extreme theoretical and practical importance, that brings needed attention to our small domain.My CACM article on P v. NP has proven very popular in great part because of the excitement of the unknown. In that article I wrote "Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not." For much as I'd like to see a proof that P ≠ NP, I would also hate to lose that mystique. Who would read an article on the status of P v. NP if the status was "proven 15 years ago"?Let me note one correction in the article pointed out by Andrew Appel: It was Armin Haken, and not his father Wolfgang, that showed that there are no short resolutions proofs for the pigeon hole principle.
Posted By Lance to Computational Complexity at 9/11/2009 05:51:00 AM