In fact back when proving software was just beginning, there was a famous paper showing that the “proofs” of fairly trivial programs (things like GCD) published in peer review journals were wrong, and the programs proved correct had bugs.
However, I was at Illinois at the time the four color theorem was proved, and I taught Appel’s son, who did a lot of the coding, assembler. I believe in his code. 
I also taught Haken’s daughter, who was even smarter.
Fermat was never the #1 problem. It has little importance for mathematics or even number theory. Goldbach is even more insignificant. Hard, yes, but of no significance. The importance of the Fermat conjecture lay in the math that was developed to solve it. There is an even better conjecture called the abc conjecture that you can google and Fermat would be a trivial consequence. Poincare was almost certainly #2 before it fell. But #1 and very likely to remain #1 unless it is solved is the Riemann hypothesis. It is hard to explain in layman’s terms but it can be shown to be equivalent to the statement that if you look at all the square-free numbers up to a large bound, roughly the same number of them have an odd number of divisors. The “roughly” has a precise statement but somewhat tecnical. It is almost that the difference is no more than the square root of the bound, but that’s not quite it. Ok, it is that if N is the bound, then for all epsilon > 0, it is less that N to the power 1/2 + epsilon.
Eh, for this crowd, it shouldn’t be too hard to give a direct statement of the Riemann Hypothesis:
It is known that there is a unique function Zeta(s) from complex numbers to complex numbers with the following three properties:
A: It is defined for all inputs except 1
B: Wherever it is defined, it has a derivative
C: Wherever the infinite series 1/1^s + 1/2^s + 1/3^s + 1/4^s + … converges, the value of Zeta(s) equals the sum of that series
It’s also known that every negative even integer is a zero of this function. The Riemann Hypothesis is the assertion that all the other zeros have real component 1/2.
As it happens, that infinite series in part C) can also be expressed, thanks to the fundamental theorem of arithmetic, as reciprocal of the infinite product (1 - 1/2^s) * (1 - 1/3^s) * (1 - 1/5^s) * (1 - 1/7^s) * …, with one factor for each prime. This then mediates many connections between the Riemann Hypothesis and statements about the prime numbers, lending it many important consequences.
Child’s play. All of the ones mentioned. The clear winner is:
Three guys pay 10 bucks each for a hotel room…
ducks and runs
Cecil solved that one. Now if we can just get him to solve the Riemann hypothesis…
I think the reason it wouldn’t make the list is that everyone is pretty sure they know the answer. If the proof gave some great new insights into computational complexity, that would be useful.
As an aside, what is the significance of solving one of these problems? Is it just a bit of theory for student of mathematics to test themselves against or are there further benefits down the road?
The 2007 Gödel prize went to a couple guys who showed essentially that any proof that P is not equal to NP will require significant insight. There’s an article here with some details, and the recent complexity book by Arora and Barak has a chapter related to this.
The methods developed for their solutions will be useful elsewhere. Fermat’s theorem is a perfect example–the fact that Wiles solved it is almost irrelevant given what he did along the way.
One of the more interesting open problems in computer science is the unique games conjecture. If it’s true, it implies a lot about the hardness of approximating NP-complete problems in polynomial time.
I’d say that solving Fermat’s with the math available to him when he was alive would be nice.
Thanks for the link. I haven’t done complexity stuff in a long time. I haven’t even worked with mathematicians for a long time.
It would be nice, but it may not be possible. Many people think Fermat made a mistake in his undiscovered proof.
Well if you solve one of the Millennium Problems, the significance is USD $1 million, payable to you.
Every number theorist will tell you that the Generalized Riemann Hypothesis is the most important unsolved math problem.
Scores and scores of results–some very important–have been shown to be either equivalent to or a consequence of the Generalized Riemann Hypothesis. These conditional results would instantly all be proven true if the Generalized Riemann Hypothesis were proved. Of course, disproving the Generalized Riemann Hypothesis would also be a huge accomplishment, if perhaps a little disappointing.
To be clear here: of greatest importance to number theorists is the Generalized Riemann Hypothesis. It includes the regular old Riemann Hypothesis as a special case.
I forgot to say: Artin’s Conjecture on Primitive Roots is implied by the Generalized Riemann Hypothesis.
Hilbert’s axiomatization of Geometry and development of the subject without recourse to “intuition” was found to be rather heavily depending on intuition when the proof was rewritten in Isabelle.
Many important computational problems are incredibly intractable. Predicting how a particular gene will fold, for instance, takes something like 65000 hours of computing time. If P=NP, potentially we could predict how genes fold within minutes.
Note, however, that it may be the case that P=NP but the proof was non-constructive, or P=NP and the algorithm synthesised is polynomial but has a huge exponent.
As ultrafilter notes, though, it’s possible to show that none of our standard mathematical proof techniques (notably diagonalization, which is used all over complexity theory) are useful for showing P=NP. Any proof either way will require some revolutionary insight.
If P=NP, then there exists a very simple proof of that fact. All one has to do is provide a polynomial algorithm for some NP-complete problem. Surely, “proof by example” isn’t considered an esoteric or insightful technique?
Now, if (as most suspect) P != NP, then the proof of that might be very difficult indeed, or even impossible.
Not at all so. There are non-constructive proofs all over the place in Complexity Theory. In particular, there are non-constructive proofs for several problems related to P vs. NP. Just because one method of proof may exist does not imply that all methods of proof have to be similar.
For over 30 years there has been a growing body evidence that any proof of P vs. NP (in either direction) won’t be at all straightforward. (And there’s already been a cite in this very thread about this.)
Fixing some proof system, it is conceivable that, although program A (and others) is actually a polynomial algorithm for some NP-complete problem, it is not possible within this system to prove that program A always correctly solves that NP-complete problem. In this way, it is possible for P = NP to be true but unprovable (from some particular proof system).
Or, less drastically, it is possible that one can prove that program A always correctly solves that NP-complete problem, but that this proof is not at all simple (is esoteric, requires an insightful technique, and so on). Indeed, such lack of simplicity is likely to be unavoidable because, as CSRP points out, any proof either way regarding P vs. NP must, as opposed to most familiar proofs, fail to relativize to arbitrary oracles.
“Many people” is probably an understatement. Given that virtually all of the most brilliant mathematicians since Fermat devoted some brain-cycles to the problem over the centuries, given that several “truly marvellous” proofs were advanced which contained subtle but fatal flaws, and given that the eventual proof was long and complicated, the general (if not universal) consensus is that Pierre de Fermat was mistaken. Or he was playing a truly magnificent prank on future generations.
(This, incidentally, is a separate result from the Razborov-Rudich result mentioned above)