Interactive proof systems


http://www.cs.princeton.edu/theory/complexity/ipchap.pdf

What is intuitively required from a theorem-proving procedure? First, that it is
possible to “prove” a true theorem. Second, that it is impossible to “prove” a false
theorem. Third, that communicating the proof should be efficient, in the following
sense. It does not matter how long must the prover compute during the proving
process, but it is essential that the computation required from the verifier is easy.”
Goldwasser, Micali, Rackoff 1985

Example 8.4
As an example for a probabilistic interactive proof system, consider the following scenario: Marla
claims to Arthur that she can distinguish between the taste of Coke (Coca-Cola) and Pepsi. To
verify this statement, Marla and Arthur repeat the following experiment 50 times: Marla turns her
back to Arthur, as he places Coke in one unmarked cup and Pepsi in another, choosing randomly
whether Coke will be in the cup on the left or on the right. Then Marla tastes both cups and states
which one contained which drinks. While, regardless of her tasting abilities, Marla can answer
correctly with probability 1
2 by a random guess, if she manages to answer correctly for all the 50
repetitions, Arthur can indeed be convinced that she can tell apart Pepsi and Coke.