Here's an example of such a protocol, for the problem of graph (non)isomorphism. Verifier: Here are two graphs, A and B. Are they isomorphic? (Same except for

Here's an example of such a protocol, for the problem of graph (non)isomorphism. Verifier: Here are two graphs, A and B. Are they isomorphic? (Same except for relabeling vertices) Prover: No, they're different. Verifier: Here's one of the graphs, with the vertices relabeled uniformly randomly. Which one was it? Prover: It was A. (Repeat 100 times) Verifier: Ok, you got them all right. I believe you. Here, we've forced the prover into a situation where if it's lying, and graphs A and B are in fact isomorphic, it can't know which graph we started with, before permuting. As a result, it can only guess which graph we started with and hope to get lucky, and we'll catch it with very high probability. In contrast, if the verifier was telling the truth, it could figure out which graph we started with, and always answer correctly. Here it is impossible for the prover to make its lie, "the graphs are not isomorphic" consistent with its later inability to tell them apart, after random permutation. This kind of 'catching in a lie' is how interactive proofs typically work.