A short certificate is a static object. A conversation allows a verifier instead to choose a fresh challenge after it has received information. The challenge must be designed so that an honest prover can answer it, while a dishonest prover cannot predict it well enough to make a false claim persuasive. Graph nonisomorphism gives a concrete example: the verifier can generate a disguised graph efficiently even though it does not know how to recognize its source on its own.
Two roles and two probabilities
Definition 9.1.1
(Interactive proof for a language)
An interactive proof system has a randomized verifier running in polynomial time and a prover without a computational time bound. They exchange messages on common input , and the verifier accepts or rejects. For a language , completeness requires that some prover makes accept each with probability at least . Soundness requires that every prover makes accept each with probability at most . Probabilities are taken over the verifier's random choices, and also over the prover's choices if it uses randomness. The class consists of languages with such a polynomial-time verifier and polynomially many messages.
The quantifiers have different jobs. Completeness permits an honest prover chosen for the whole language, not an efficient algorithm that the verifier can execute. Soundness is adversarial: it must hold against every possible prover strategy. The verifier's computation and the total transcript must be polynomially bounded; the prover may solve computationally difficult questions to decide what message to send. To enforce the bound even against a malicious prover, the verifier reads at most its prescribed polynomial message limit plus one bit and rejects an oversized message. The input is fixed when success probability is evaluated. This is a worst-case requirement, not an average over graph pairs.
A nondeterministic certificate is a special case of this picture: the prover sends a certificate and the verifier checks it deterministically. Interaction is useful only if the verifier's private choices affect which response is required. Public communication does not mean that a choice hidden from the prover must be revealed before it is used.
Certificates as one-message conversations
The definition already contains a useful comparison with nondeterministic verification. It is worth proving the inclusion rather than treating the prover as an unexplained oracle: an NP witness gives the prover's message, and the deterministic verifier remains in charge of the final decision.
Proposition 9.1.2
(NP is contained in IP)
Every language in has an interactive proof with perfect completeness and perfect soundness, using one prover message and a deterministic polynomial-time verifier.
Proof
(Proof)
Choose a polynomial-time verifier and polynomial certificate bound for the given NP language. The prover sends a candidate certificate; the interactive verifier rejects if it is too long and otherwise evaluates on the input and the certificate. If the input is in the language, some short certificate is accepted, so the honest prover sends it and acceptance is certain. If the input is outside the language, no certificate is accepted, regardless of the prover's strategy, so rejection is certain. The verifier uses polynomial time. This proves the inclusion; it does not prove that every interactive proof has a short static certificate.
Worked example 9.1.3
(A certificate for a small clique)
Suppose the input graph has vertices and edges , and the claimed clique size is . A prover sends the list . The verifier checks that the entries are distinct vertices and then checks the three pairs against the input; all are edges, so it accepts. If the graph had no clique of size , every possible three-vertex list would either repeat a vertex or contain a missing edge. The soundness argument concerns all possible messages, not merely the list an honest prover happens to send.
Graph isomorphism and relabeling
Definition 9.1.4
(Graph isomorphism and nonisomorphism)
Two finite simple graphs and are isomorphic if a bijection of their vertices preserves both adjacency and nonadjacency. When both have vertices, we may label each vertex set by ; a permutation of those labels produces a relabeled graph. Graph nonisomorphism, abbreviated GNI here, is the language of pairs of finite simple graphs that are not isomorphic.
Pairs with different vertex counts are trivially nonisomorphic and can be accepted immediately, so the protocol below concerns equal-size graphs. A size-zero pair consists of two empty graphs and is therefore isomorphic; the verifier can reject it immediately.
The prover sees both graphs. The verifier chooses a uniformly random bit and an independent uniformly random permutation of the labels, sends , and asks which input graph it came from. The verifier accepts if the answer equals . For an efficient implementation of a uniform permutation, use a standard random-permutation procedure; an ideal uniform choice is used in the probability argument below. A bounded-error implementation from fair bits requires care about exact sampling, and can instead use a sufficiently accurate polynomial-time sampler with the error accounted for in the soundness bound.
Worked example 9.1.5
(A path or a triangle?)
Let be the path on three vertices and the triangle. Relabeling changes vertex names but not the number of edges. The path always has two edges and the triangle three, so even the verifier can identify the source by counting edges. This illustrates the messages in the protocol, although the point of the general protocol is that an efficient verifier need not know a simple distinguishing invariant for arbitrary input graphs.
Sampling a permutation with bounded running time
The ideal uniform permutation makes the main idea easy to see, but a polynomial-time verifier using a fixed number of fair bits must implement its choices. A uniformly random integer in a range whose size is not a power of two cannot in general be produced exactly from a fixed number of fair bits. Instead we control the approximation error explicitly.
Proposition 9.1.6
(A bounded-bit sampler is close to uniform)
For every positive , there is a sampler that uses polynomially many fair bits and runs in polynomial time, and whose output distribution on the permutations of objects differs from uniform by at most in total variation distance.
Proof
(Proof by coupling the choices)
Use the usual swap construction: for , select an index from and swap it with the item currently in position . If these choices are independent and uniform, each of the sequences of choices has probability and gives a different permutation, so the output is uniform.
Let be the least integer with . To choose an index in a range of size , draw fair bits to form a uniform integer from through , take its remainder modulo , and add . Each index occurs either the floor or ceiling of times. Its probability differs from by less than , so the total variation distance of this single choice from uniform is at most . Couple that choice to an ideal uniform choice so that they disagree with probability at most . Across all steps, the union bound gives disagreement probability at most . If no step disagrees, the output permutations agree. Hence the output distributions are within in total variation. The sampler uses at most bits and polynomial time.
For an isomorphic pair, couple the actual sampler to an ideal one. Against any fixed prover strategy, the interaction transcript and acceptance agree whenever the sampled permutations agree. The ideal probability of successful guessing is , so the actual one is at most . The coupling may be performed anew conditional on any previous transcript. Two fresh rounds therefore have soundness at most , while completeness remains . This proves the protocol meets the fixed-fair-bit model rather than assuming an exact non-dyadic random choice.
Completeness: a truthful prover can identify the orbit
Suppose and are not isomorphic. A relabeling of is isomorphic to and cannot be isomorphic to the other input: otherwise composition of the two isomorphisms would show . An unbounded prover can enumerate permutations and decide which graph is isomorphic to . It returns with certainty. Thus the protocol has perfect completeness on nonisomorphic inputs.
The word “unbounded” does real work. An honest prover may inspect all permutations; no polynomial-time algorithm for that search is assumed. The verifier only samples a permutation, relabels the graph, and compares a one-bit answer with its private bit.
Soundness: the challenge hides its origin
Proposition 9.1.7
(One-round graph nonisomorphism protocol)
For equal-size input graphs, the protocol above accepts every nonisomorphic pair with probability under an honest prover. If the input graphs are isomorphic, under the ideal uniform sampler any prover, however powerful, is accepted with probability exactly when it always sends a bit. The bounded-bit implementation and repetition described here give an interactive proof for GNI.
Proof
(Why isomorphic graphs give the same distribution)
Suppose for a fixed permutation . If , the sent graph is . If , it is . Multiplication by the fixed permutation is a bijection on the finite permutation group, so is uniformly distributed whenever is. Hence the distribution of is identical for the two values of .
The prover sees the input and , but supplies no information about the fair bit . For any fixed response rule based on that view, the response equals with probability . The same conclusion holds after averaging over any private randomness of the prover. A non-bit response may simply be rejected, in which case the probability is at most .
Proof X-ray
Why the challenge carries no information
The non-obvious step is to compare distributions of whole labeled graphs rather than invariants such as edge counts. The hypothesis is spent in exactly one place: it turns the challenge for into . Multiplying by the fixed is a bijection of the permutation group, so a uniform stays uniform and the two challenge distributions coincide. Two other ingredients carry weight. The permutation and the bit are chosen independently, so a distribution of that does not depend on means that is independent of . And stays private until the prover has answered, so the answer is a function of , the input and the prover's own randomness, none of which depends on ; it matches with probability exactly .
The argument closes without any bound on the prover's running time. It would break if were not uniform, because the two distributions of could then differ, or if were revealed, because the answer would then be a function of .
This argument is information-theoretic: no limit on the dishonest prover's running time is used. The important equality is between whole distributions of labeled graphs, not merely between edge counts or any one graph invariant. Even if many permutations produce the same labeled graph, multiplication by pairs the permutations producing that graph in the two cases, with their multiplicities intact.
Counterexample mode
Without the random relabeling the challenge reveals its source
Suppose the verifier skipped the permutation and simply sent . Take , let have the single edge and the single edge . These graphs are isomorphic, via the permutation exchanging and , so the input is not in GNI. Yet as labeled graphs they are different, so a prover who sees reads off at once and is accepted with probability . The soundness proof needs the uniform : after relabeling, the graph sent has the same distribution whichever input it came from.
Repetition and adaptive strategies
Under ideal uniform sampling, run the challenge independently twice and accept only if both answers are correct. Completeness remains , while soundness becomes at most , below the required . The cheating prover may use the entire previous transcript to choose its next response. Conditional on that transcript, however, the next bit and permutation are fresh and the two conditional distributions of the new challenge are still identical. Its conditional chance of success is at most . Multiplying the two conditional bounds gives ; similarly rounds give soundness at most .
A verifier that revealed before the prover answered would destroy this argument. The challenge graph is public, but the random origin bit is private until after the response. Keeping these two pieces of information separate is the central design choice.
Worked example 9.1.8
(A relabeled copy gives no evidence about the bit)
Let both inputs be the same labeled four-cycle. A particular relabeling might arise from several permutations because the cycle has symmetries. Nevertheless, for each permutation generating when , the identical permutation generates when . The conditional distributions coincide, and seeing does not change the prior probability of either bit. The argument for different but isomorphic labeled copies uses the fixed relabeling to obtain the same pairing.
Common mistake
(An honest prover is not enough for soundness)
Showing that a truthful prover can answer is only completeness. If the graphs are isomorphic, a cheating prover may use any strategy whatsoever, including one tailored to the full transcript. The soundness proof must show that no such strategy can recover a hidden bit from two identical distributions.
What this does and does not establish
The protocol proves GNI belongs to . It does not prove that GNI is outside , that graph isomorphism has no polynomial-time algorithm, or that is strictly larger than . The major theorem requires additional machinery and is not proved here. These distinctions matter because an inclusion or a successful protocol is a positive construction; it does not automatically establish a separation of complexity classes.
Practice and solutions
Quick check
(Why do nonisomorphic input graphs give disjoint sets of possible challenge graphs?)
Suppose one graph lies in both sets.
Solution · Answer
A graph in both sets would be isomorphic to each input. Composing one isomorphism with the inverse of the other would make the inputs isomorphic, contrary to hypothesis.
Quick check
(Suppose the inputs are isomorphic. What is the maximum chance of answering three fresh independent challenges correctly in succession, even with an adaptive prover?)
Multiply the conditional bounds.
Solution · Answer
Under ideal uniform sampling the bound is : after any previous transcript the next fresh challenge still has the same distribution for either hidden bit. With the bounded-bit sampler above, the corresponding bound is .
Quick check
(What fails if the verifier sends its hidden bit to the prover together with the relabeled graph?)
Ask who learns the bit.
Solution · Answer
The prover can return the supplied bit on every input, including isomorphic pairs. The verifier then accepts false claims with probability , violating soundness.