IP (complexity)

The Television & Movie Wiki: for TV, celebrities, and movies.

1 Interactive Proof Systems
2 Proof that IP = PSPACE
- 2.1 IP is a subset of PSPACE
- 2.2 PSPACE is a subset of IP
  - 2.2.1 #SAT is a member of IP
  - 2.2.2 TQBF is a member of IP
3 References
4 External links

Interactive Proof Systems

In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Goldwasser, et al. in 1985. An interactive proof system consists of two machines, a prover, P, which presents proofs of membership and a verifier, V, that check that the presented proof is correct. The prover is unbound in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of the input. Given an input <math>n</math> these two machines exchange a polynomial number, <math>p(n)</math>, of messages and once the interaction is completed, the verifier must decide whether or not the presented string is in the language. More formally:

For any language <math>L</math>, function <math>P</math>, and input string <math>w</math>, <math>L \in IP \Rightarrow \exists V, P | \forall \tilde{P}, w</math>:

<math>w \in L \Rightarrow Pr[V \leftrightarrow P\ accepts\ w] \ge

\frac{2}{3}</math>

<math>w \not \in L \Rightarrow Pr[V \leftrightarrow \tilde{P}~

accepts\ w] \le \frac{1}{3}</math>

The Arthur-Merlin protocol is similar in nature, except that the random bit string is public to both the prover and the verifier, rather than privately held by the verifier. AM was introduced by Laszlo Babai, and shown to be equivalent to IP by Shafi Goldwasser and Michael Sipser.

In the following section we prove that <math>IP = PSPACE</math>, an important theorem in computational complexity, which demonstrates that an interactive proof system can be used to decide whether a string is a member of a language in polynomial time, even though the traditional PSPACE proof may be exponentially long.

[edit]

Proof that IP = PSPACE

In order to prove that IP and PSPACE are equal, we show that IP is a subset of PSPACE and also that PSPACE is a subset of IP, and hence the two are equivalent. In order to demonstrate that <math>IP \subseteq PSPACE</math>, we present a simulation of an interactive proof system by a polynomial space machine. To prove that <math>PSPACE \subseteq IP</math>, we show that the PSPACE-complete language TQBF is in IP. Both parts of the proof are adapted from Sipser.

[edit]

IP is a subset of PSPACE

Let A be a language in IP. Now, assume that on input w with length n, A's verifier V exchanges exactly <math>p=p(n)</math> messages. We now construct a machine M that simulates V and is in PSPACE. To do this, we define our machine as follows:

<math>Pr[V\ accepts\ w] = max_P Pr[V\ \leftrightarrow P accepts\ w]</math>

By the definition of <math>IP</math>, we have <math>Pr[V\ accepts\ w] \ge \frac{2}{3}</math> if <math>w \in A</math> and <math>Pr[V\ accepts\ w] \le \frac{1}{3}</math> if <math>w \not \in A</math>.

Now, it must be shown that the value can be calculated in polynomial space. Here we take <math>M_j</math> denote to denote this sequence of messages, <math>m_1\# \ldots \#m_j</math>, exchanged by the prover and the verifier, and we generalize the interaction of V and P to start with an arbitrary message stream <math>M_j</math>. We take <math>(V \leftrightarrow P)(w,r,M_j) = accept</math> if <math>M_j</math> can be extended with the messages <math>m_{j+1}</math> through <math>m_p</math> such that:

For <math>j \leq i < p</math>, where i is even, <math>V(w, r, M_i) = m_{i+1}</math>
For <math>j \leq i < p</math>, where i is odd, <math>P(w, r, M_i) = m_{i+1}</math>
The final message <math>m_p</math> in the message history is accept

In other words, when <math>i</math> is even, the verifier sends a message, when it is odd, the prover sends a message, and the final message is to accept. The first two rules ensure that the message sequence is valid, and the third ensures that this message sequence leads to an accept.

Next, further generalizing the earlier definitions, and taking a random string <math>r</math> of length <math>p</math>, we define:

<math>Pr[V \leftrightarrow P\ accepts\ w\ starting\ at\ M_j] = Pr[(V \leftrightarrow P)(w,r,M_j) = accept] </math>

Now, we can define:

<math>Pr[V accepts\ w\ starting\ at\ M_j] = max_P Pr[V \leftrightarrow P\ accepts\ w\ starting\ at\ M_j] </math>

and for every <math>0 \leq j \leq p</math> and every message history <math>M_j</math>, we inductively define the function <math>N_{M_j}</math>:

<math> N_{M_j} = \begin{cases}

 0: j = p\ and\ m_p = reject\\
 1: j = p\ and\ m_p = accept\\
 max_{m_{j+1}} N_{M_{j+1}}: j < p\ and\ j\ is\ odd\\
 wt-avg_{m_{j+1}} N_{M_{j+1}}: j < p\ and\ j\ is\ odd\\

\end{cases} </math>

where the the term <math>wt-avg_{m_{j+1}}N_{M_{j+1}}</math> is defined as follows:

where <math>Pr_r</math> is the probability taken over the random string <math>r</math> of length <math>p</math>. This expression is the average of <math>N_{M_{j+1}}</math>, weighted by the probability that the verifier sent message <math>m_{j+1}</math>.

Take <math>M_0</math> to be the empty message sequence, here we will show that <math>N_{M_0}</math> can be computed in polynomial space, and that <math>N_{M_0} = Pr[V\ accepts\ w]</math>. First, to compute <math>N_{M_0}</math>, an algorithm can recursively calculate the values <math>N_{M_j}</math> for every j and <math>M_j</math>. Since the depth of the recursion is p, only polynomial space is necessary. The second requirement is that we need <math>N_{M_0} = Pr[V accepts w]</math>, the value needed to determine whether w is in A. We use induction to prove this as follows.

We must show that for every <math>0 \leq j \leq p</math> and every <math>M_j</math>, <math>N_{M_j} = Pr[V\ accepts\ w\ starting\ at M_j]</math>, and we will do this using induction on j. The base case is to prove for <math>j = p</math>. Then we will use induction to go from p down to 0.

The base case <math>(j = p)</math> is fairly simple. Since <math>m_p</math> is either accept or reject, if <math>m_p</math> is accept, <math>N_{M_p}</math> is defined to be 1 and Pr[V accepts w starting at <math>M_j</math>] = 1 since the message stream indicates acceptance, thus the claim is true. If <math>m_p</math> is reject, the argument is very similar.

For the inductive hypothesis, we assume that for some <math>j + 1 \leq p</math> and any message sequence <math>M_{j+1}</math>, <math>N_{M_{j+1}} = Pr[V\ accepts\ w\ starting\ at\ j+1]</math> and then prove the hypothesis for <math>j</math> and any message sequence <math>M_j</math>.

If j is even, <math>m_{j+1}</math> is a message from V to P. By the definition of <math>N_{M_j}</math>, <math>N_{M_j} = \sum_{m_{j+1}}(Pr_r[V(w,r,M_j)=m_{j+1}] N_{M_{j+1}})</math>. Then, by the inductive hypothesis, we can say this is equal to <math>\sum_{m_{j+1}}(Pr_r[V(w,r,M_j)=m_{j+1}] * Pr[V\ accepts\ w\ starting\ at\ M_{j+1}])</math>. Finally, by definition, we can see that this is equal to <math>Pr[V\ accepts\ w\ starting\ at\ M_j]</math>.

If j is odd, <math>m_{j+1}</math> is a message from P to V. By definition, <math>N_{M_j} = max_{m_{j+1}} N_{M_{j+1}}</math>. Then, by the inductive hypothesis, this equals <math>max_{m_{j+1}} * Pr[V\ accepts\ w\ starting\ at\ M_{j+1}]</math>. This is equal to <math>Pr[V\ accepts\ w\ starting\ at\ M_j]</math> since:

<math>max_{m_{j+1}} Pr[V\ accepts\ w\ starting\ at\ M_{j+1}] \leq Pr[V\ accepts\ w\ starting\ at\ M_j]</math>

because the prover on the right-hand side could send the message <math>m_{j+1}</math> to maximize the expression on the left-hand side. And:

<math>max_{m_{j+1}} Pr[V\ accepts\ w\ starting\ at\ M_{j+1}] \geq Pr[V\ accepts\ w\ starting\ at\ M_j]</math>

Since the same Prover cannot do any better than send that same message. Thus, this holds whether <math>i</math> is even or odd and the proof that IP <math>\subseteq</math> PSPACE is complete.

Here we have constructed a polynomial space machine that uses the best prover <math>P</math> for a particular string <math>w</math> in language <math>A</math>. We use this best prover in place of a prover with random input bits because we are able to try every set of random inptut bits in polynomial space. Since we have simulated an interactive proof system with a polynomial space machine, we have shown that IP <math>\subseteq</math> PSPACE, as desired.

[edit]

PSPACE is a subset of IP

In order to illustrate the technique that will be used to prove <math>PSPACE \subseteq IP</math>, we will first prove a weaker theorem, which was proven by Lund, et al.: <math>\#SAT \in PSPACE</math>. Then using the concepts from this proof we will extend it to show that <math>TQBF \in PSPACE</math>. Since TQBF <math>\in</math> PSPACE-Complete, and <math>TQBF \in IP</math> then PSPACE <math>\subseteq</math> IP.

[edit]

#SAT is a member of IP

We begin by showing that <math>\#SAT \in IP</math>, where:

<math>\#SAT = \{ \langle \phi, k \rangle \mid \phi</math> is a cnf-formula with exactly <math>k</math> satisfying assignments <math>\}</math>.

First we use arithmetization to map the boolean formula with <math>n</math> variables, <math>\phi(b_1, b_2, ..., b_n)</math> to a polynomial <math>p_\phi(x_1, x_2, ..., x_n)</math>, where <math>p_\phi</math> mimics <math>\phi</math> in that <math>p_\phi</math> is 1 if <math>\phi</math> is true and 0 otherwise provided that the variables of <math>p_\phi</math> are assigned Boolean values. The Boolean operations <math>\vee</math>, <math>\wedge</math>, and <math>\neg</math> used in <math>\phi</math> are simulated in <math>p_\phi</math> by replacing the operators in <math>\phi</math> as shown in the table below.

Arithmetization rules for converting a Boolean formula <math>\phi(b_1, b_2, ..., b_n)</math> to a polynomial <math>p_\phi(x_1, x_2, ..., x_n)</math>
<math>a \wedge b</math>	<math> ab</math>
<math>a \vee b</math>	<math> a*b \equiv 1 - (1 - a)(1 - b) </math>
<math>\neg a</math>	<math>1 - a</math>

As an example, <math>\phi = a \wedge b \vee \neg c</math> would be converted into a polynomial as follows:

<math> p_\phi = a \wedge b \vee \neg c </math>
<math> p_\phi = a \wedge (1 - (1-b)(1-(1-c))) </math>
<math> p_\phi = a (1 - (1-b)(1-(1-c))\dot) </math>
<math> p_\phi = a - (ac-abc\dot) </math>

The operations <math>ab</math> and <math>a*b</math> each result in a polynomial with a degree bounded by the sum of the degrees of the polynomials for <math>a</math> and <math>b</math> and hence, the degree of any variable is at most the length of <math>\phi</math>.

Let <math>f_i</math> be a function and <math>F</math> be a finite field with at least <math>q \le 2^n</math>, for <math>0\leq i\leq m</math> and <math>a_1, ..., a_i\in F</math>. Set <math>f_{i}(a_1, ..., a_i)</math> equal to the number of satisfying assignments of <math>\phi</math> such that each <math>x_j = a_j</math> for <math>j\leq i</math>. For <math>0 \leq i \leq m</math> and for <math>a_1, ..., a_i \in F</math> let <math>f_i(a_1, ..., a_i) = \Sigma _{a_{i+1}, ..., a_m \in \{0, 1\}} p(a_1, ..., a_m)</math>. Note that the value of <math>f_0</math> is still the number of satisfying assignments of <math>\phi</math>. Also note that <math>f_i</math> is a univariate function, where the <math>i^{th}</math> element is the variable.

Now the protocol for <math>\#SAT</math> works as follows:

Phase 0:
The prover <math>P</math> choses a prime <math>q > 2^n</math> and computes

<math>f</math>, it then sends <math>q</math> (along with a short proof of <math>q</math>'s primality) and <math>f_0()</math> to the verifier <math>V</math>. <math>V</math> checks that <math>q</math> is prime and that <math>f_0() = k</math>.

Phase 1:
<math>P</math> sends the coefficients of <math>f_1(z)</math> as a

polynomial in z. <math>V</math> verifies that the degree of <math>f_1</math> is less than <math>n</math> and that <math>f_0 = f_1(0) + f_1(1)</math>. (If not <math>V</math> rejects). <math>V</math> now sends a random number <math>r_1</math> from <math>F</math> to <math>P</math>.

Phase i:
<math>P</math> sends the coefficients of <math>f_1(r_1, ...,

r_{i-1}, z)</math> as a polynomial in <math>z</math>. <math>V</math> verifies that the degree of <math>f_1</math> is less than <math>n</math> and that <math>f_{i-1}(r_1, ..., r_{i-1}) = f_i(r_1, ..., r_i, 0) + f_i(r_1, ..., r_i, 1)</math>. (If not <math>V</math> rejects). <math>V</math> now sends a random number <math>r_i</math> from <math>F</math> to <math>P</math>.

Phase m+1:
<math>V</math> evaluates <math>p(r_1, ..., r_m)</math> to compare to

the value <math>f_m(r_1, ..., r_m)</math>. If they are equal <math>V</math> accepts, otherwise <math>V</math> rejects.

If <math>\phi</math> has <math>k</math> satisfying assignments, clearly <math>V</math> will accept. If <math>\phi</math> does not have <math>k</math> satisfying assignments we assume there is a prover <math>\tilde P</math> that tries to convince <math>V</math> that <math>\phi</math> does have <math>k</math> satisfying assignments. We show that this can only be done with low probability.

To prevent <math>V</math> from rejecting in phase 0, <math>\tilde P</math> has to send an incorrect value <math>\tilde f_0()</math> to <math>P</math>. Then, in phase 1, when <math>V</math> chooses a random <math>r_1</math> to send to <math>P</math>, Pr[<math>\tilde f_1(r_1) = f_1(r_1)] < n^{-2}</math>, for <math>n \geq 10</math>. This is because a polynomial in a single variable of degree at most <math>d</math> can have no more than <math>d</math> roots (unless it always evaluates to 0). So, any two polynomials in a single variable of degree at most <math>d</math> can be equal only in <math>d</math> places. Since <math>F > 2^n</math> the chances of <math>r_1</math> being one of these values is at most <math>n/2^n</math>.

Generalizing this idea for the other phases we have for each <math>1 \leq i \leq m</math> if <math>\tilde f_{i-1}(r_1, ..., r_{i-1}) \not=f_{i-1}(r_1, ..., r_{i-1})</math>, then for <math>n \geq 10</math> and for <math>r_i</math> chosen randomly from <math>F</math>, Pr[<math>\tilde f(r_1, ..., r_i) = f_i(r1, ..., r_i)] \leq n^{-2}</math>. There are <math>m</math> phases, so the probability that <math>\tilde P</math> is lucky because <math>V</math> selects a convenient <math>r_i</math> is at most <math>1/n</math>. So, no prover can make the verifier accept with probability greater than <math>1/n</math>. We can also see from the definition that the verifier <math>V</math> operates in probabilistic polynomial time. Thus, <math>\#SAT \in IP</math>.

[edit]

TQBF is a member of IP

In order to show that PSPACE is a subset of IP, we need to choose an PSPACE-Complete problem and show that it is in IP. Once we show this, then it clear that PSPACE <math>\subseteq</math> IP. The proof technique demonstrated here is credited to Adi Shamir

We know that TQBF is in PSPACE-Complete. So let <math>\psi</math> be a quantified boolean expression:

where <math>\phi</math> is a CNF formula. Then <math>Q_i</math> is a quantified, either <math>\exists</math> or <math>\forall</math>. Now <math>f_i</math> is the same as in the previous proof, but now it also includes quantifiers.

<math>f_i(a_1, ..., a_i) = \begin{cases} f_i(a_1, a_2,...a_m) = 1~if~ Q_{i+1}x_{i+1}...Q_mx_m[\phi(a_1,a_2...a_i)]~is~true\\ 0~otherwise \end{cases} </math>

Here, <math>\phi(a_1,a_2,...,a_i)</math> is <math>\phi</math> with <math>a_1</math> to <math>a_i</math> substituted for <math>x_1</math> to <math>x_i</math>. Thus <math>f_0()</math> is the truth value of <math>\psi</math>. In order to arithmetize <math>\psi</math> we must add the following identities: <math>Q_{i+1} = \forall replace\ with\ f_i(a_1,a_2,....a_i) = f_{i+1}(a_1,a_2,...,a_i,0)\cdot f_{i+1}(a_1,a_2,...,a_i,1)</math>
<math>Q_{i+1} = \exists replace\ with\ f_i(a_1,a_2,....a_i) = f_{i+1}(a_1,a_2,...,a_i,0) * f_{i+1}(a_1,a_2,...,a_i,1) </math>

where we define x * y = 1-(1-x)(1-y).

By using the method described in <math>\#SAT</math>, we must face a problem that for any <math>f_i</math> the degree of the resulting polynomial may double with each quantifier. In order to prevent this, we must introduce a new reduction operator R which will reduce the degrees of the polynomial without changing their behavior on Boolean inputs.
So now before we arithmetize <math>\psi = Q_1 x_1 Q_2x_2...Q_mx_m[\phi]</math> we introduce a new expression:

Or written another way:

<math>\psi' = S_1 y_1 S_2 y_2...S_m y_m[\phi]
S_i \in \{ \forall ,\exists , R\}
y_i \in \{ x_1,x_2,...x_m\} </math>

Now for every i <math>\leq</math> k we define the function <math>f_i</math>. We also define <math>f_k(x_1,x_2,....x_m)</math> to be the polynomial <math>p(x_1,x_2,...x_m)</math> which is obtained by arithmetizing <math>\phi</math>. Now in order to keep the degree of the polynomial low, we define <math>f_i</math> in terms of <math>f_{i+1}</math>:

<math>S_{i+1} = \forall replace\ with\ f_i(a_1,a_2,....a_i) = f_{i+1}(a_1,a_2,....a_i,0)\cdot f_{i+1}(a_1,a_2,....a_i,1) </math>
<math>S_{i+1} = \exists replace\ with\ f_i(a_1,a_2,....a_i) = f_{i+1}(a_1,a_2,....a_i,0) * f_{i+1}(a_1,a_2,....a_i,1) </math>
<math>S_{i+1} = R replace\ with\ f_i(a_1,a_2,....a_i,a) = (1-a)f_{i+1}(a_1,a_2,....a_i,0) + a f_{i+1}(a_1,a_2,....a_i,1) </math>

Now we can see that the reduction operation R, doesn't change the degree of the polynomial. Also it is important to see that the <math>R_x</math> operation doesn't change the value of the function on boolean inputs. So <math>f_0</math> is still the truth value of <math>\psi</math>, but the <math>R_x</math> value produces a result that is linear in x. Also after any <math>Q_ix_i</math> we add <math>R_{x_1}...R_{x_i}</math> in <math>\psi'</math> in order to reduce the degree down to 1 after arithmetizing <math>Q_i</math>.

Now let's describe the protocol. If <math>n</math> is the length of <math>\psi</math>, all arithmetic operations in the protocol are over a field of size <math>n^4</math> where <math>n</math> is the length of <math>\psi</math>.

Phase 0:

<math>P \rightarrow V</math>: P sends <math>f_0</math> to V. V checks that <math>f_0 = 1</math> and rejects if not.

Phase 1:

<math>P \rightarrow V</math>: P sends <math>f_1(z)</math> to V. V uses coefficients to evaluate <math>f_1(0)</math> and <math>f_1(1)</math>. Then it checks that the polynomial is at most <math>n</math> and that the following identities are true:

<math>f_{0}() =

\begin{cases} \{ f_{1}(0)\cdot f_{1}(1) ~if~ S = \forall \\ f_{1}(0) * f_{1}(1) ~if~ S = \exists. \end{cases}</math>

<math>f_{0}() = (1-r)f_{1}(0) + rf_{1}(1) ~if~ S = R.</math>

If either fails then reject.

Phase i:

<math>P \rightarrow V</math>: P sends <math>f_i(r_1,r_2...r_{i-1},z)</math> as a polynomial in <math>z</math>. <math>r_1</math> denotes the previously set random values for <math>r_1,r_2...r_{i-1}</math>
V uses coefficients to evaluate <math>f_i(r_1,r_2...r_{i-1},0)</math> and <math>f_i(r_1,r_2...r_{i-1},1)</math>. Then it checks that the polynomial degree is at most <math>n</math> and that the following identities are true:

<math>f_{i-1}(r_1,r_2...r_{i-1}) = \{

f_{i}(r_1,r_2...r_{i-1},0)\cdot f_{i}(r_1,r_2...r_{i-1},1) ~if~ S = \forall.</math>

<math>f_{i}(r_1,r_2...r_{i-1},0) * f_{i}(r_1,r_2...r_{i-1},1) ~if~

S = \exists.</math>

<math>f_{i-1}(r_1...r) = (1-r)f_{i}(r_1,r_2...r_{i-1},0) +

rf_{i}(r_1,r_2...r_{i-1},1) ~if~ S = R.</math>

If either fails then reject.
<math>V \rightarrow P</math>: V picks a random <math>r</math> in <math>F</math> and sends it to P. (If S=R then this <math>r</math> replaces the previous <math>r</math>).
Goto phase i+1 where P must persuade V that <math>f_i(r_1,...,r)</math> is correct.

Phase k+1:

V evaluates <math>p(r_1,r_2,...,r_m)</math>. Then it checks if <math>p(r_1,r_2,...,r_m) == f_k(r_1,r_2,....r_m)</math> If they are equal then V accepts, otherwise V rejects.

This is the end of the protocol description.

If <math>\psi</math> is true then V will accept when P follows the protocol. Likewise if <math> \tilde{P} </math> is a malicious prover which lies. Then if <math>\psi</math> is false, then <math> \tilde{P} </math> will need to lie at phase 0 and send some value for <math>f_0</math>. So if at phase i, V has an incorrect value for <math>f_{i-1}(r_1,...)</math> then <math>f_i(r_1,...0)</math> and <math>f_i(r_1,...1)</math> must also be incorrect, and so forth. And since the probability for <math> \tilde{P} </math> to get lucky on some random <math>r</math> is at most the degree of the polynomial divided by the field size: <math>n/n^4</math>. The protocol runs through <math>O(n^2)</math> phases, so the probability that <math> \tilde{P} </math> gets lucky at some phase is <math>\leq \frac{1}{n}</math>. So if <math> \tilde{P} </math> is never lucky, then V will reject at phase k+1.

Since we have now shown that both IP <math>\subseteq</math> PSPACE and PSPACE <math>\subseteq</math> IP, we can conclude that IP = PSPACE as desired.

[edit]

References

1. Babai, L. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation . ACM, New York, 1985, pp. 421-429.

2. Goldwasser, S., Micali, S., Rackoff, C. Theknowledge complexity of interactive proof-systems. In Proceedings of 17th Annual ACM Symposium on Theory of Compution. ACM, New York, 1985, pp. 291-304.

3. Goldwasser, S., Sipser, M. Private coins versus public coins in interactive proof systems. In Proceedings of the 18th Annual ACM Symposium on Theory of Computation. ACM, New York, 1986, pp. 59-68.

4. Lund, C., Fortnow, L.. Karloff, H., Nisan, N. Algebraic methods for interactive proof systems. In Proceedings of 31st Symposium on the Foundations of Computer Science. IEEE, New York, 1990, pp. 2-90.

5. Shamir, A. IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992.

6. Sipser, Micheal. "Introduction to the Theory of Computation", Boston, 1997, pg. 392-399.

[edit]