Computer Assisted Proofs- still controversial?



Kenneth Appel, of Appel-Haken Four Color Theorem Fame, died recently. See here for an obit.

In 1972 I read that the four-color theorem was an open problem. From what I read it seemed like there was some progress on it (e.g., results like `if its false the graph has to be yah-big) but it seemed to be years away from being solved. I assumed that a new idea was needed to solve it.

Then, in 1976, it was SOLVED by Appel-Haken. From what I read it wasn't so much a new idea but very clever use of old ideas and a computer program. I also heard that it was just at the brink of what computers could do at the time, and that it would have taken 1200 grad student hours. (There is a good description of the proof on Wikipedia here.)

At the time I heard there were objections to the proof. Later when I read some of them they didn't seem like real objections. They boiled down to either

I wish there was a shorter proof. This is true, but not a reason to object.

It can't be hand checked. I trust a computer-checker MORE THAN a human checker

We don't know WHY its true. This is a more reasonable objection- but we do know how they got it down to a finite number of cases, so I'm happy with that.

In 1996 Robertson, Sanders, Seymour, Thomas was obtained a simpler proof. In 2005 Werner and Gontheir formalized the proof inside Coq- a proof assistant. To quote Wikipedia This removed the need to trust the various computer programs used to verify particular cases;it is only necessary to trust the Coq Kernel At this point I doubt anyone seriously doubts that the theorem has been proven.

There have been more computer-assisted proofs since then. See here for a list of some of them. That article also claims that such proofs are controversial and not always accepted. Is this really true? I thought the controversy was gone except for the topic of the next paragraph.

A famous computer assisted proof (or perhaps ``proof'') is the Kepler Conjecture. In 1998 Thomas Hale claims to have proven it. The proof involved rather complex computer calculations. The referees say they are 99% sure its true. Here's hoping an easier proof is found.

Computer assisted proofs may become more common. I just hope we still know WHY things are true.

Was Appel-Haken the first use of computer assisted proofs? I doubt it, but it was likely the first one to have an impact. It was important to know that this kind of proof could be done.

Is there a much shorter proof? A combinatorist once told me that since the function


f(n) = max size of proofs of statements of length n


grows faster than any computable functions, there have to be some statements that have very log proofs; and perhaps the four color theorem is one of them.






 •  0 comments  •  flag
Share on Twitter
Published on April 30, 2013 18:20
No comments have been added yet.


Lance Fortnow's Blog

Lance Fortnow
Lance Fortnow isn't a Goodreads Author (yet), but they do have a blog, so here are some recent posts imported from their feed.
Follow Lance Fortnow's blog with rss.