In a talk of John Watrous on Friday in Tutte’s seminar, he proposed the above problem as an interesting example of the power of interactive proofs over classical proofs. To make it precise, suppose that I believe that Coke and Pepsi taste differently plus I can actually feel the difference; and you are really curious if I am right. Well, how can I convince you (give you a “proof”) that they taste differently? The proof needs to have the property that if I am right then you should detect it, and if I am wrong then you should detect it with high probability (say, 99.9 percent).

.

.

.

It is difficult, eh?

.

.

.

No, it is simple. Just make me blindfold, give me 1000 glasses of Coke/Pepsi and I have to categorize them. If I do it correctly, then you will be convinced that I can feel the difference. This is the point: The proof is done by “interaction between you (verifier) and me (prover),” and not by simply giving a certificate (as in the case of classical proof). Well, if I am a liar, then there is a tiny probability that I can fool you; but we usually ignore such small probabilities in life!

### Like this:

Like Loading...

*Related*

Tags: computational complexity

This entry was posted on March 13, 2010 at 7:36 pm and is filed under story. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply