In the graph non-isomorphism interactive proof, the verifier secretly picks one of two graphs, applies a random permutation, and shows it to the prover, asking 'which graph did I pick?' Why does this protocol have sound rejection of a cheating prover?
AThe prover's computation is polynomial-time bounded, preventing it from checking all permutations
BIf the graphs are actually isomorphic, any permutation of one is indistinguishable from a permutation of the other, so the prover can only guess — and each wrong guess is caught
CThe verifier's private coins prevent the prover from computing which graph was permuted
DThe prover must commit to its answer before seeing the permuted graph
Soundness comes from the information-theoretic structure. If the two graphs are isomorphic (making the claim of non-isomorphism false), then a permutation of Graph 1 looks exactly like a permutation of Graph 2 — they are indistinguishable. A cheating prover sees a random graph that could have come from either, so it can only guess with probability 1/2. Repeated rounds drive the cheating probability exponentially to zero. The prover's computational power is irrelevant — even an all-powerful cheating prover cannot do better than random guessing when it has no information to distinguish the two cases.
Question 2 Multiple Choice
The result IP = PSPACE implies which of the following about interactive proofs?
ANP = PSPACE, since NP ⊆ IP = PSPACE
BInteractive proofs can verify only problems that have short static certificates
CInteractive proofs can decide any problem in PSPACE, including those with no known short static certificate (no NP witness)
DAll PSPACE-complete problems can be solved in polynomial time with a trusted oracle
IP = PSPACE means the class of problems verifiable by an interactive proof system exactly equals PSPACE. This is far larger than NP: PSPACE includes problems like quantified Boolean formula (QBF) where there is no known polynomial-size certificate, requiring the full alternating quantifier structure to be verified. That IP = PSPACE does NOT imply NP = PSPACE; what it shows is that interaction (randomized challenges and responses) can substitute for certificates that are too large to write down. The prover's unbounded power handles the computation; the verifier's randomness provides soundness.
Question 3 True / False
In the Arthur-Merlin model, making the verifier's random coins public (visible to the prover before it responds) strictly weakens the interactive proof system compared to private-coin protocols.
TTrue
FFalse
Answer: False
Counterintuitively, public and private coins yield the same expressive power: AM = IP. The prover in an interactive proof is computationally unbounded, so it can simulate all possible outcomes of the verifier's private randomness anyway — the secrecy of the coins provides no additional security against an all-powerful prover. The verifier's power comes from the structure of the interaction (challenges and responses), not from hiding its randomness. This equivalence, proven by Goldwasser and Sipser, is one of the more surprising results in complexity theory.
Question 4 True / False
Soundness in an interactive proof system requires that no cheating prover can convince the verifier to accept a false claim with any nonzero probability; even accepting with probability 0.01 would violate soundness.
TTrue
FFalse
Answer: False
Soundness is defined probabilistically: for any false claim, no cheating prover can make the verifier accept with probability greater than some soundness error (commonly 1/3 or 1/2). Small soundness error is acceptable because the protocol can be repeated to amplify soundness: k independent repetitions reduce the soundness error from 1/3 to (1/3)^k. Perfect soundness (error = 0) is not required and would be an unnecessarily strict definition. The gap between completeness (≥ 2/3) and soundness (≤ 1/3) is what makes the proof system meaningful.
Question 5 Short Answer
Explain why the prover being computationally unbounded does NOT mean the prover can always convince the verifier to accept false claims in an interactive proof system.
Think about your answer, then reveal below.
Model answer: The prover's unbounded computation is not the bottleneck — what limits a cheating prover is the verifier's randomness. For false claims, there is no valid strategy that works for all possible random challenges. The verifier's random choices create a space of possible transcripts, and a cheating prover must commit to answers before seeing future challenges. The soundness condition ensures that for any fixed (possibly dishonest) prover strategy, the verifier's randomness makes most transcripts lead to rejection. Computational power cannot manufacture valid answers to challenges that depend on random coins not yet revealed.
This is the key conceptual point: the prover has power to compute anything, but it cannot predict the future random challenges. For graph non-isomorphism: even an all-powerful cheating prover, when the graphs are isomorphic, sees a uniformly random graph (since permutations of isomorphic graphs are identically distributed) and has no information to base its answer on. More generally, for false statements in IP, the sum-check protocol structure ensures that a cheating prover must commit to polynomial values that are inconsistent with the claimed sum, and the verifier's random evaluation point will detect the inconsistency with high probability.