14. Randomized Verification

Randomness is a useful tool in the design of algorithms. As we see in this lecture, it is also a useful tool in the design of proof verifiers.

MA

The notion of verifiers that led us to the definition of the class \(\mathbf{NP}\) has a natural extension to probabilistic Turing machines.

Definition. A probabilistic verifier is a Turing machine with two additional tapes on top of its usual input tape: one certificate tape, and a randomness tape.

The probabilistic verifier \(V\) \(\epsilon\)-decides the language \(L\) for some \(\epsilon \ge 0\) if it always halts and:

• \(x \in L \Rightarrow\) \(\exists c\) \(\Pr_r[ V \mbox{ accepts } (x,c,r)] \ge 1 - \epsilon\)
• \(x \notin L \Rightarrow\) \(\forall c\) \(\Pr_r[ V \mbox{ accepts } (x,c,r) ] \le \epsilon\).

\(\mathbf{MA}\) is the set of languages that can be \(\frac13\)-decided by polynomial-time probabilistic verifiers.

The class \(\mathbf{MA}\) is named for Merlin and Arthur. We can picture the process of verifying a language as an interactive process between an all-powerful being (Merlin) and a computationally bounded individual (King Arthur, who has only access to standard randomized computers in Camelot and really needs any computation done on them to be completed in polynomial time to make sure he gets the result before the next meeting of the Knights of the Round Table.) This view of the verification process might not be entirely aligned with the original legends regarding Merlin and Arthur, however, because in this setting Merlin is always trying to get Arthur to accept with as large a probability as possible, even when the input is not in the language. Arthur’s task, then, is to design a verifiable protocol that will let him efficiently accept whenever \(x \in L\), and yet will not fool him no matter what certificate Merlin produces when \(x \notin L\).

Notably, in the interactive interpretation of the class \(\mathbf{MA}\), Merlin does not have access to the random string that will be generated by Arthur’s probabilistic verifier; the certificate is produced first. This means that there are some languages that are not obviously in \(\mathbf{NP}\) that can be shown to be in \(\mathbf{MA}\).

Define the succinct Minimum Arithmetic Circuit Size Problem to be

Proposition. \(\textsf{SuccinctMACSP} \in \mathbf{MA}\).

Proof. Consider the probabilistic verifier that asks for \(\left|\left<C'\right>\right|\) as the certificate. The verifier then checks that the encoding of \(C'\) is indeed smaller than that of \(C\), and then uses the \(\mathbf{BPP}\) algorithm for \(\textsf{PIT}\) to check that \(C\) and \(C'\) represent the same polynomial.

Interactive Proofs

Randomness, along with the interactive view of proof verification, also let us extend the class \(\mathbf{NP}\) even further. Instead of just using randomness to probabilistically verify the certificate provided by Merlin, Arthur could use it to formulate challenges to Merlin that a certificate must address. This notion can be formalized in the following way.

Definition. A 2-round interactive verifier is a probabilistic Turing machine with an additional read-write oracle tape. It has a special Query Oracle state that it can use once during its computation. When it does so, the contents of the oracle is changed to a certificate (that depends on the input and the query written on the oracle tape). From that point on, the verifier proceeds exactly as with standard probabilistic verifiers.

The class \(\mathbf{IP[2]}\) is the set of languages that can be \(\frac13\)-decided by polynomial-time 2-round interactive verifiers.

It is again easier to view this model of verification in its interactive form. Arthur now gets to use his random bits and the input to decide what query string \(q\) to send to Merlin. Merlin responds with a certificate \(c\) that depends on the input \(x\) and the query \(q\), but not on the random string \(r\) that Arthur sees. (This model is called a private randomness model of interactive proofs for this reason.) Then Arthur uses the input \(x\), the randomness string \(r\), the query \(q\), and the returned certificate \(c\) to determine if he accepts or not.

As the name of the definition and the corresponding class \(\mathbf{IP}[2]\) suggest, we can also consider interactive proofs with more rounds of interaction. But, as it turns out, even this simple 2-round setting is enough to verify languages that are not known to be in \(\mathbf{MA}\).

Define the Graph Non-Isomorphism language to be the set

of encodings of graphs that are not isomorphic to each other. This language is easily seen to be in \(\mathbf{coNP}\), because I can give you the permutation of vertices of \(G\) that makes it equal to \(H\) when the graphs are isomorphic to each other. We can also show directly that it is in \(\mathbf{IP[2]}\).

Theorem. \(\textsf{GraphNonIso} \in \mathbf{IP[2]}\).

Proof. Consider the following simple randomized 2-round protocol:

• Arthur picks \(G\) or \(H\) uniformly at random.
• Then Arthur permutes the vertices of his chosen graph uniformly at random.
• The resulting graph is sent to Merlin.
• Merlin must then tell Arthur whether the graph is a permutation of \(G\) or of \(H\).
• Arthur accepts if and only if Merlin is correct.

When \(G \not\cong H\), then permuting the vertices does not prevent Merlin from determining which of the graphs was chosen in the first step of the algorithm. (Recall that Merlin has unbounded computational power, so he can for example do a brute-force search over all possible permutations of \(G\) to see if any of them are equivalent to the graph received in the query.)

But when \(G \cong H\), then the graph obtained by randomly permuting the vertices of \(G\) or of \(H\) has the same distribution no matter which of the two graphs was selected in the first step. As a result, Merlin can do no better than random guessing and will be able to fool Arthur with probability at most \(1/2\).

One last technical detail: to make sure that the verifier errs with probability less than 1/3, the above argument is not quite sufficient. But it’s easily fixed: simply do every step twice (in parallel), so that Arthur picks two graphs (possibly the same one twice), two random permutations of the vertices, and Merlin must determine which original graphs were selected in both instances to generate the query. This causes the error probability in the case of isomorphic graphs to be at most \((1/2)^2 = 1/4\).

AM

What happens if we consider the setting where the all-powerful being that generates the certificate not only knows the input but also the random string that Arthur generated? Formalizing this setting leads to a definition that is very similar to the one considered in introducing \(\mathbf{MA}\). We again have probabilistic verifiers, but now we change the definition of what language they decide in the following way.

Definition. The probabilistic verifier \(V\) \(\epsilon\)-\((\Pr \exists)\)decides the language \(L\) for some \(\epsilon \ge 0\) if it always halts and:

• \(x \in L \Rightarrow\) \(\Pr_r[ \exists c: V \mbox{ accepts } (x,c,r)] \ge 1 - \epsilon\)
• \(x \notin L \Rightarrow\) \(\Pr_r[ \exists c: V \mbox{ accepts } (x,c,r) ] \le \epsilon\).

Note that the order of the quantifier and \(\Pr[\cdot]\) are reversed from the earlier definition. In practice, what this means is that the certificate can now be customized for each random string \(r\), instead of being forced to choose a single certificate that is good for most random strings.

\(\mathbf{AM}\) is the set of all languages that can be \(\frac13\)-\((\Pr \exists)\)decided by a polynomial-time probabilistic Turing machine.

Theorem. \(\mathbf{MA} \subseteq \mathbf{AM}\).

Proof. The key idea is to again use success amplification.

Fix any \(L \in \mathbf{BPP}\). Let \(V\) by a polynomial-time probabilistic verifier for \(L\), and let \(\ell(n)\) be the maximum length of certificates considered by \(V\) on inputs of length \(n\). We can design \(V'\) to run \(O(\ell(n))\) independent instances of \(V\) in parallel on any input \(x\) of length \(n\) so that \(V'\) \(\frac13 2^{-\ell(n)}\)-decides \(L\).

Consider now \(V'\) as a \((\Pr \exists)\)-verifier. In this setting, Merlin now can see the randomness used by \(V'\) and potentially use this knowledge to customize the choice of certificate it returns.

• When \(x \in L\), Merlin can simply ignore this extra information and return the same certificate \(c\) that it returns in the standard verification setting. In this case,

\[\Pr_r[ \exists c : V' \mbox{ accepts } (x,c,r) ] \ge 1 - \frac13 2^{-\ell(n)} \gg \frac23.\]

• When \(x \notin L\), Merlin can return different certificates for different choices of \(r\). But by the union bound,

\[\Pr_r[ \exists c: V' \mbox{ accepts } (x,c,r) ] \le \sum_{c \in \{0,1\}^{\ell(n)}} \Pr_r[ V' \mbox{ accepts } (x,c,r) ] \le 2^{\ell(n)} \cdot \frac13 2^{-\ell(n)} = \frac13.\]

Therefore, \(V'\) \(\frac13\) \((\Pr \exists)\)-decides \(L\).

In fact, though we will not prove it here, \(\mathbf{AM}\) is surprisingly powerful: it contains not only \(\mathbf{MA}\) but also \(\mathbf{IP[2]}\) and the extension of that class to any constant number of rounds.

Theorem. For any constant \(k \ge 2\), \(\mathbf{AM} = \mathbf{IP[}k\mathbf{]}\).

Eric Blais ©2024 — Last edited on Mar. 5, 2024