A certificate is chosen to convince a verifier, while randomness is chosen to make it difficult for a false certificate to pass. The order of those choices matters. If the prover writes one message before seeing the random coins, the message must withstand a random test selected later. If the prover sees the coins first, the prover can tailor a response to the particular test. We will define both settings carefully and prove that, after sufficiently strong amplification, the first kind of protocol can be simulated by the second.
All languages below are subsets of . A verifier is a deterministic polynomial-time algorithm that receives an input, a message and a string of independent uniform random bits. The polynomial bounds on message and randomness lengths are fixed with the verifier. A prover is computationally unrestricted, but must obey the message-length bound. For readability we use completeness and soundness ; these constants can be changed by amplification when the verifier's random tests are independent.
A message before the random test
Definition 9.4.1
(The class MA)
A language is in if there are polynomials and a polynomial-time predicate such that, for every input of length ,
A shorter message can be encoded with padding and a length delimiter. Its content is fixed before the random string is sampled. The yes and no conditions quantify over all inputs of their respective types, not only over typical inputs or a chosen input distribution.
Worked example 9.4.2
(A coloring certificate)
Let the input be a finite graph with vertices explicitly listed. A message assigns one of three colors to each vertex. The verifier checks every edge and accepts exactly if its endpoints have different colors; it need not use its random bits. On a 3-colorable graph some message is always accepted. On a non-3-colorable graph every message is always rejected. This is an MA protocol with perfect completeness and soundness, obtained from an ordinary NP witness. An invalid color or malformed encoding is rejected.
Proposition 9.4.3
(Basic inclusions into MA)
Every language in and every language in belongs to .
Proof
(Proof)
For an NP language, use a polynomial-size witness as the message and run the deterministic polynomial-time verifier, ignoring the random bits. On a yes-instance an accepting witness has acceptance probability one; on a no-instance every witness has probability zero.
For a BPP language, ignore the message and run the BPP decider using the verifier's coins. Its success guarantee is at least on each fixed input. In particular every message has the same acceptance probability, so on no-instances all messages obey soundness. This gives both inclusions without assuming that NP and BPP coincide or that either contains the other.
Public coins before a response
Definition 9.4.4
(The class AM)
In a two-message public-coin protocol, Arthur first sends the random string to Merlin; Merlin then sends . Equivalently, a language is in AM if a polynomial-time predicate and polynomial message and randomness bounds satisfy
Here may depend on the revealed . Because the message space is finite, the event is equivalent to the existence of an unrestricted response strategy that succeeds on that coin string. Soundness says that even the best such strategy succeeds with probability at most . The randomness is public; a private-coin interactive protocol needs its own definition and analysis.
Concept lensCombinatorial
Rows and columns of the acceptance table
For a fixed input, write a table of acceptance bits with one row for each message and one column for each random string . MA asks for a single row with at least of its entries equal to (yes-instances), or for every row to have at most ones (no-instances). AM counts instead the fraction of columns containing at least one , which must be at least or at most . The two classes differ in whether the prover picks a row or a cell in each column.
Worked example 9.4.5
(Why the order of choices matters)
Take one random bit and one message bit , and let accept exactly when . If the message is fixed first, either fixed message is accepted with probability . If the random bit is revealed first, choosing succeeds with probability one. This finite predicate illustrates the change from to ; it is not by itself a proof that MA and AM are different classes.
Common mistake
(The same soundness bound need not survive public coins)
Suppose every fixed message fools a random test with probability at most . It does not follow that the probability that some message fools the test is at most . Different messages can succeed on different random strings. For instance, let and be two-bit strings and let the test accept exactly when : each fixed passes with probability , yet for every some passes, so the probability that some message passes is . One must bound the union of their success events, or use a different argument. The proof below amplifies until a union bound over every possible message is affordable.
Worked example 9.4.6
(The graph-nonisomorphism challenge)
In the following ideal experiment, given two graphs on the same number of vertices, Arthur chooses one uniformly, applies a uniformly random permutation, and sends the resulting graph. Merlin identifies which original graph was selected. If the graphs are nonisomorphic, an unrestricted Merlin can identify the isomorphism class and always answer correctly. If they are isomorphic, the challenge distribution is the same under either choice, so no response strategy succeeds with probability above . Independent repetition brings the latter probability below ; a separate interactive-proofs unit proves the distribution and repetition claims in detail. The random permutation is public only through the challenge graph in this particular protocol; this example motivates interactive verification but does not by itself establish the public-coin AM definition above.
This paragraph first describes an ideal uniform-permutation experiment. Exact uniform sampling from permutations cannot generally use a fixed finite number of fair bits. To obtain a bounded-time fair-bit verifier, use the sampler proved in the graph-nonisomorphism unit: its permutation distribution is within of uniform in total variation. For every prover strategy a round then succeeds with probability at most on isomorphic graphs. The same bound holds conditional on any previous transcript, so two fresh rounds have soundness at most ; completeness stays one. The ideal bound above must not be asserted as an exact bound for that approximate sampler.
Why MA is contained in AM
The following proof uses the usual Hoeffding bound for independent – variables: if their common mean is at most , the probability that their average reaches is at most , and the corresponding lower-tail bound holds when the mean is at least . We cite this concentration inequality without proof. The independence is across repetitions for one fixed message.
Theorem 9.4.7
(Amplification before revealing the coins)
.
Proof
(Proof)
Let with verifier and message length . For input length , choose and sample independent random strings . Define to accept a message exactly when a strict majority of the computations accepts. Arthur sends all random strings before receiving . Their combined length and the running time are polynomial in .
If , select an MA witness whose original acceptance probability is at least . For this one fixed witness the outcomes are independent. Hoeffding gives probability at most that its acceptance count is at most half. Thus with probability above , the message works; an adaptive Merlin can certainly send it.
If , fix a particular message . Its original acceptance probability is at most , so the probability it passes the majority test is at most . There are exactly possible messages. By the union bound, the probability that even one message passes is at most
This is precisely the soundness condition against a prover that chooses after seeing all the coins. We did not assume independence between success events for different messages; the union bound does not require it. The resulting public-coin protocol proves the inclusion.
Proof X-ray
Why the repetition count must grow with the message length
Three ingredients are used, each exactly once. Completeness is applied to a single witness , so the yes-case needs no union bound. Soundness is applied message by message, and only afterwards are the failure events added. The one non-routine move is the choice : the per-message error must beat the number of messages , and indeed because . With a constant the argument collapses: for the bound is , which exceeds as soon as and says nothing. The proof closes because soundness is quantified after the coins: the existence of a message is absorbed into the union, so Merlin's freedom to tailor to costs only the factor .
The verifier uses a strict majority, so a tie is a rejection. On a yes-instance the lower-tail estimate includes ties among the possible errors; on a no-instance the upper-tail estimate bounds an even larger event that includes ties. No separate tie-breaking randomness is needed.
The amplification count depends on witness length. A constant number of repetitions could reduce the failure probability for each fixed message while leaving exponentially many candidate messages to be tried after the coins are revealed. The linear number of repetitions above makes the per-message error exponentially small enough to pay for all candidates. This is a proof of containment, not a proof that the two classes are equal or unequal.
Amplifying a public-coin protocol
Amplification must respect the order of messages. In an AM protocol Merlin sees all the public coins and can coordinate the responses across repetitions. It would be incorrect to declare Merlin's response-dependent acceptance events independent. Instead, for each random challenge, ask whether any response could pass it. That question depends only on the challenge, so the resulting indicators are independent across independently sampled challenges.
Proposition 9.4.8
(Polynomially small error for AM)
Let have a public-coin AM protocol with completeness at least and soundness at most . For any polynomial with nonnegative integer values, has a public-coin AM protocol with both error probabilities below on inputs of length .
Proof
(Proof)
Choose independent random strings and send their concatenation. Merlin returns one candidate response for each string, and the verifier accepts exactly when a strict majority of the individual checks accept. For each , define if at least one allowed response could pass the original check on the th random string. Since is fixed and the challenges are independent, the indicators are independent, regardless of how Merlin might choose actual responses.
On a yes-instance, . For every sequence with a majority of good challenges, an unrestricted prover can choose a passing response for each good challenge, so the amplified verifier accepts. On a no-instance, . Whatever joint response strategy Merlin uses, it cannot make a bad challenge pass, so a majority of accepted checks requires a majority of the to be one. Hoeffding bounds either error by . The total communication and running time remain polynomial. The proof does not require the prover's chosen responses to be independent.
Worked example 9.4.9
(A response may depend on all challenges)
Imagine two public challenge strings . A prover could choose its first answer using both strings, rather than only . This extra coordination still cannot make the first check pass if no allowed answer exists for . Thus the indicator of whether an answer exists provides an upper bound on every coordinated strategy. In the amplified construction, the indicators are sampled independently even though the messages need not be.
The same distinction appears in the inclusion proof. There we bound a union over messages after sampling one long random tape; in the AM amplification proof we instead define one existence event per independent challenge and bound a majority of those events. Both arguments start with a fixed input and keep the prover's full freedom visible. Neither replaces the explicit completeness and soundness quantifiers with an informal claim that repetition always works.
Adding rounds of public coins and responses changes the class only when the number of rounds grows.
A path to generalization
What changes with more rounds?
Adding rounds of public coins and responses changes the class only when the number of rounds grows.
Protocols with a constant number of public-coin rounds can be reorganized into the two-message form studied here, so they define the same class AM. When the number of rounds is allowed to grow polynomially with the input length, the class becomes PSPACE. These are standard results proved elsewhere; the structure that changes is the count of alternations between Arthur's coins and Merlin's messages.
Practice and solutions
Quick check
(For the equality predicate exactly when , compute the best fixed-message success probability and the best response-after-coins probability.)
Compare one fixed bit with one revealed bit.
Solution · Answer
Each fixed bit agrees with a uniform random bit with probability . Once the bit is revealed, choosing the same bit succeeds with probability one.
Quick check
(Why does an NP verifier give MA soundness for every possible message on a no-instance?)
Recall what NP soundness says about witnesses.
Solution · Answer
NP soundness states that no witness causes the deterministic verifier to accept a no-instance. Ignoring randomness gives acceptance probability zero for every message.
Quick check
(In the containment proof, if , how many length-two messages are in the union bound, and how many repetitions does the displayed choice use?)
Evaluate and .
Solution · Answer
There are messages. The chosen number of repetitions is ; the union-bound upper estimate is , which is less than .
Quick check
(Explain why the acceptance events for distinct messages need not be independent in the union-bound argument.)
What do all messages have in common in the experiment?
Solution · Answer
They are all evaluated against the same sequence of revealed random strings. One message's success can therefore be correlated with another's. The union bound only adds their individual probability bounds and remains valid without independence between events.
Quick check
(If a verifier's random string is revealed before the message, what must soundness bound?)
Where does the quantifier over messages now sit?
Solution · Answer
It must bound the probability, over the public random string, that there exists any allowed response which makes the verifier accept. This covers every response strategy, including one selected after seeing the coins.
Quick check
(Does prove ?)
Which direction of inclusion has been shown?
Solution · Answer
No. The inclusion says every MA language has an AM protocol. It does not prove the reverse inclusion, nor does it exhibit a language separating them.