Reminds me of the 1993 Scientific American article "The Death of Proof" by John Horgan. Horgan talked about experimental proofs and computer-assisted proofs as well as interactive proofs. Most notably there was a sidebar story titled "A Splendid Anachronism?" on Wiles' then recent proof of Fermat's last theorem. It's nice to report that fifteen years later the traditional mathematical proof is not dead yet.
Back to Helger's question. I have no problems with the probabilistic aspect of interactive proofs. With a proper source of randomness, one can make the error so small it gets washed out by other cosmic effects. I have no problems with the interaction in an interactive proof either. I learn all proofs interacting, either with a person or a paper.
But a proof is something to be savored and shared and interactive proofs prevent both. One can understand a traditional mathematical proof at many levels of details, the same way one can read Shakespeare either as a quick read or looking at it in depth to find new meanings. Interactive proofs require proofs are the purely logical level, sort of like explaining the Mona Lisa by giving a bit map of the image. And in the end the verifier only gets to learn that there is a Mona Lisa, possibly without any idea what it looks like.
Moreover when you hear a great proof you want to tell the world, much the way you want to share a good joke, something I've occasionally done on this blog (proofs and a bad joke now and then). But an interactive proof of tautology or a zero-knowledge proof of satisfiability one cannot share. You believe but you cannot convince others.
Nothing against the theory of interactive proofs and zero-knowledge. What we can do with them is quite surprising, the applications, particularly to approximation algorithms and cryptography, are quite amazing and I'm lucky to have played a role in their development. But the proofs that interactive proofs do what they do will always excite me much more than the proofs they generate.
It's true that a ZKP, by its very nature, can't be shared; but regarding your other point, the ability to view a proof as a work of art that can be effectively conceptualized by a human reader stems in large part from its imprecision. The reader is expected to infer much of the elided content in a typical published mathematical proof; otherwise we'd be reading volumes of syntactic symbol-pushing for the most elementary of results. Indeed, peer review would be essentially unnecessary for mathematics if proofs were specified at a level at which they could be mechanically verified.
ReplyDeleteWhich raises the question, is it possible to have an imprecise but easier-to-conceptualize zero-knowledge proof?
Reminds me of the 1993 Scientific American article "The Death of Proof" by John Horgan.
ReplyDeleteProofs aren't dead, but Scientific American as we once knew it is dead. Horgan's article was a sign that the end was coming.
Proofs aren't dead, but Scientific American as we once knew it is dead. Horgan's article was a sign that the end was coming.
ReplyDeleteIt got even worse after Horgan: in 1999, Scientific American published an article by Copeland and Proudfoot called "Alan Turing's Forgotten Ideas in Computer Science". It is quite possibly the stupidest article I've ever seen published in any mainstream magazine. They actually claim that the field of computer science forgot about the idea of an oracle, but that it was now being revived in the quest for "hypercomputation" (i.e., computation beyond what Turing machines can do), and that scientists were currently hard at work trying to build physical oracles for the halting problem.
I actually thought it might be an April Fool's Day joke (the article was published in April), but I met Copeland at a conference and he's every bit as crazy/ignorant as you'd expect from the article.
That was when I cancelled my subscription to Scientific American. During the 1990's, there were only two articles in areas I was enough of an expert in to evaluate with complete confidence, and they were both garbage. That really made me wonder how many equally silly articles I had accepted without question, and I found it was no fun to read the magazine while constantly wondering whether the articles were credible or whether the authors were even competent.
It's sad, since I loved Scientific American when I was a kid.