Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Proofs Still Not Dead

Expand Messages
  • Lance
    Helger Lipmaa points to Justin Beldin s essay on the epistemology of Interactive/Zero-Knowledge proofs and asks my opinion on the general topic. Reminds me of
    Message 1 of 1 , Dec 4, 2008
      Helger Lipmaa points to Justin Beldin's essay on the epistemology of Interactive/Zero-Knowledge proofs and asks my opinion on the general topic.

      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.

      Posted By Lance to Computational Complexity at 12/04/2008 06:23:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.