Posts Tagged ‘computational complexity’

Does Coke and Pepsi taste differently?

March 13, 2010

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!

The PCP Theorem, and computational complexity

February 8, 2010

One reason I like computational complexity is because it’s mysterious: you see surprising results that don’t agree with your common sense. The first example was the equality NL = co-NL, which I saw a few years ago, and has a very elegant proof. And the second example was the PCP e, i.e. NP = PCP (log n, 1), which is quite surprising, and the proof is perhaps very complicated. That’s why you can never be sure that NP\P is nonempty, even if  everyone believes it.

For almost the same reason, I liked probability theory when I was in high-school: it is mysterious, and there were lots of paradoxical problems related to probability. Well, when I studied formal probability theory (Kolmogorov axioms etc.) there wasn’t any paradoxes anymore (fortunately?), but I still like it, because of its surprisingly strong applications in graph theory and algorithms.