Example 10.1

Example 10.2

The above two examples demonstrate simple interactive proof systems for some problems in coNP that are not known to be complete for coNP. The next example shows a more complicated interactive proof system for a -complete problem, with a hint of the general theorem that all problems in PSPACE have interactive proof systems (Theorem 10.26).

Example 10.3

Weak Interactive Proof System for PERM.

Input: An Boolean matrix A and an integer q. (The prover needs to prove that .)

Initially, let and .

Stage i, . A_i is an matrix. The prover sends integers , , to the verifier, where B_i,j is the submatrix of A_i obtained by deleting the first row and the jth column of A_i. Next, the verifier verifies that

(10.1)

If the above equation does not hold, then the verifier rejects the input (A,q). Otherwise, the verifier chooses a random and lets and . He/she sends and to the prover and goes to the next stage.

Stage n. The verifier has a matrix A_n and an integer q_n. The verifier accepts the input if and only if .

Assume that . Then the prover can always compute the correct values at each stage i and, hence, can prove that with probability 1.

On the other hand, when , the error probability could be very large. More precisely, assume that at stage i, . Then, the prover could give correct values and only one incorrect value q_i,j and could still satisfy (10.1). The probability that the verifier chooses this incorrect value to be is . As a whole, the probability that all pairs are incorrect in all stages i is only . Thus, the above proof system is too weak.

To remedy this problem, we modify the above proof system to reduce the error probability. Let us call a pair (C,r) of a matrix C and an integer r incorrect if . We have just seen that if at each stage i, the verifier only recursively tests the correctness of a random pair , then the error probability is too large. On the other hand, if the verifier recursively tests every pair at stage i, then it would take an exponential amount of time. The idea here is to combine all pairs to create a single pair that, with a large probability, is incorrect as long as one of the original pairs is incorrect. Therefore, the total number of pairs considered is polynomially bounded, and yet the error probability is kept small.

Interactive Proof System for PERM.

Input: (A,q).

Choose a large prime number p such that . (It could be done in polynomial time by the verifier; or, the prover could send the prime number, together with a short proof that it is indeed a prime, to the verifier.)

Let and .

Stage i, . The prover needs to prove that .

Substage . The prover finds , and sends them to the verifier, where B_i,j is the submatrix of A_i obtained by deleting the first row and the jth column of A_i. Next, theverifier verifies that

If the above equation does not hold, then the verifier rejects the input (A,q). Otherwise, let and , and go to substage .

Substage , . The verifier forms an linear-polynomial matrix

and sends D(x) to the prover, asking forits permanent f(x) (a polynomial of degree ). When the verifier receives the permanent polynomial f(x) from the prover, he/she checks that and ; if either equation fails, he/she rejects the input. Otherwise, the verifier chooses a random integer and let (i.e., C is the integer matrix obtained by substituting the integer a for the variable x in D) and .

At the end of substage , let and .

Stage n. The verifier has a matrix A_n and an integer q_n. The verifier accepts the input if and only if .

First notice that an Boolean matrix A must have , and so, for any , implies . Thus, we do not lose any generality using arithmetic modulo p. (In the following lemma, we say (C,r) is incorrect if and only if .) Next, we observe again that if , then the prover can always compute correct permanent values, including the permanent f of the polynomial matrix D in each substage , and wins the game with probability 1. We only need to prove that when , the probability of the prover winning the game is small.

Lemma 10.4

Proof

We observe that if is incorrect, then after substage , one of the pairs is incorrect. Now, following the above lemma, the error in the pair at stage i will be passed to the next pair at stage i + 1 with probability . The total error probability of the above interactive proof system is thus bounded by

which is negligible when n is reasonably large.

From the above examples, we can see that an interactive proof system consists of an honest verifier who wants to learn whether or not a given instance x is in a set A and an unreliable prover whose task is to answer questions of the verifier to maximize his winning probability. As the prover is potentially treacherous, it is the verifier's job to detect the cheating to minimize the error probability. Thus, it is natural to define the interactive proof systems from the verifier's point of view, that is, we define the verifier as a probabilistic machine and let the prover take the role of an oracle. Formally, we define an interactive Turing machine to be a polynomial time oracle PTM M_v that uses an oracle function f_p with the following special rule of making queries: The machine M_v makes a query y to the oracle f_p by writing on the query tape (1) the input x, (2) the whole history of queries and answers exchanged between the machine M_v and the oracle f_p, and (3) the new query y. (This special rule reflects the assumption that the prover can send a message y_i based on the input x as well as the history of the messages exchanged between the prover and the verifier.) Note that the polynomial-time bound on M_v implies that it can only work with polynomial-length-bounded oracle functions f_p. The notion of interactive proof systems can be defined by interactive TMs, working with unreliable oracles. (See Exercise 10.1 for an alternative formulation of the notion of interactive proof systems.)

Definition 10.5

The time complexity of an interactive TM is restricted to be polynomially bounded. In addition to the time complexity, an important complexity measure of an interactive proof system is the number of queries made by M_v to the oracle f_p. Recall that a computation of a probabilistic oracle machine M, relative to an oracle f, is a sequence of successive configurations of M^f, from a starting configuration to a halting configuration. We define the number of rounds of a computation of an interactive proof system to be the number of messages (queries and answers) exchanged between the machine M_v and the oracle f_p in this computation. For an integer function r, we say that a set A has an r(n)-round interactive proof system if there exists an interactive proof system for A such that the number of rounds of all the computations of the system on all x is bounded by .³

Definition 10.6

Similar to the probabilistic complexity classes RP and BPP, the classes IP and IP_k remain the same if we change the error bound 1/4 to any constant .

Proposition 10.7

Definition 10.8

The notion of the number of rounds in an Arthur–Merlin proof system is defined exactly the same as that of an interactive proof system. Here, we distinguish the proof systems in which Merlin sends the messages first from those in which Arthur sends the messages first.

Definition 10.9

Again, the classes AM and remain unchanged for any constant error probability ε > 0. We omit the proof.

Proposition 10.10

In the above, we have defined the Arthur–Merlin proof system from Arthur's point of view, that is, we view such a proof system as Arthur working with an unreliable oracle Merlin trying to prove that an instance x is in A. As Merlin knows every random bit Arthur uses and has the unlimited computational power to simulate Arthur's computation, we may also look at this proof system from Merlin's point of view. Namely, we may think that Merlin tries to convince Arthur, who is a passive verifier, that an instance x is in A by showing the complete probabilistic proof to him, where the two players share a common trustable random number generator. That is, Merlin can demonstrate the proof by playing both roles in the game: he nondeterministically generates his messages for himself and randomly generates messages for Arthur. To formalize this idea, we consider a new computational model of probabilistic NTMs.

A probabilistic NTM is an NTM M attached with a random number generator ϕ. The machine M has two nonstandard states: the nondeterministic state and the random state. When the machine enters the nondeterministic state, it generates a bit nondeterministically, and when it enters a random state, it obtains a random bit from the random number generator. We call a probabilistic NTM a Merlin machine if there exists a polynomial p such that for each input x, it always halts in moves.

To simplify the notion of the accepting probability of a Merlin machine, we assume that such a machine M has two extra read-only tapes, called the Merlin tape and the Arthur tape, in addition to the input/output/work tape. The Arthur tape is just the random-bit tape of a PTM, where a sequence of random bits is supplied by the random number generator ϕ. The Merlin tape contains the messages to be sent from Merlin to Arthur. We assume that when a Merlin machine enters the nondeterministic state, it reads the next bit from the Merlin tape and when the machine enters the random state, it reads the next bit from the Arthur tape. Thus a configuration of a Merlin machine consists of the following information: (1) the current state q, (2) the current string s in the input/output/work tape to the left of the tape head, (3) the current string t at and on the right of the tape head in the input/output/work tape, (4) the current string α on the Merlin tape (from the beginning cell to the cell scanned by the tape head), and (5) the current string β on the Arthur tape (from the beginning cell to the cell scanned by the tape head). We define the successor relation on configurations and the concept of accepting configurations similar to that for PTMs (see Section 9.2). In particular, a configuration in the random state (or in the nondeterministic state) has two successor configurations, and (or, respectively, and ) for some states q₀ and q₁.

To define the notion of the accepting probability, we first define the accepting probability of a configuration c. For any configuration , we let if q is an accepting state and if q is a rejecting state. If q is a regular deterministic state and c₁ is the unique successor configuration of c, then let . If q is a random state and c₀ and c₁ are two successor configurations of c, then let be the average of and . If q is a nondeterministic state and c₀ and c₁ are two successor configurations of c, then let be the maximum of and . For any input x, the accepting probability of a Merlin machine on x is equal to , where c_x is the starting configuration for x. We also write to denote the accepting probability of M on x. As a Merlin game always halts in polynomial time, the probability is well defined.

The concept of rounds can also be defined in a Merlin machine. We define a random round of a computation of a Merlin machine M to be a maximum-length sequence of configurations that are either in a deterministic state or in the random state. Similarly, a nondeterministic round of a computation of a Merlin machine M is a maximum-length sequence of configurations that are either in a deterministic state or in the nondeterministic state. For k ≥ 1, a k-round Merlin machine M is one all of whose computations have at most k random and nondeterministic rounds.

Proposition 10.11

10.3 AM Hierarchy Versus Polynomial-Time Hierarchy

In this section, we consider the complexity classes AM_k of sets having Arthur–Merlin proof systems of a bounded number of rounds. It is clear that these classes form a hierarchy:

We are going to see that this hierarchy collapses to the second level. In addition, they are contained in the second level of the polynomial-time hierarchy.

To begin with, we first give an alternating quantifier characterization for the AM hierarchy like that for the polynomial-time hierarchy in Theorem 3.8. Intuitively, a move by Merlin demonstrates a new piece of proof to Arthur, and so it corresponds to an existential quantifier , while a move by Arthur is simply a sequence of random bits, and to a probabilistic quantifier . (Recall that means “for at least strings y of length m,” and is the abbreviation for .)

Recall that two predicates R₁ and R₀ are complementary if R₁ implies .

Definition 10.12

A simple induction shows that complementary - and -predicates are indeed complementary if . We are going to show that if , then the predicates and are complementary AM_k-predicates. Before we prove that, we need to show that the notion of complementary AM_k-predicates remains unchanged with respect to different values r. This can be proved by the majority vote technique. As it is more involved than the proofs of Theorems 10.7 and 10.10, we give a complete proof below. In the following, we write to mean “for more than numbers .”

Lemma 10.13