NationMaster - Encyclopedia: IP (complexity)

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

n

these two machines exchange a polynomial number,

p (n)

, of messages and once the interaction is completed, the verifier must decide whether or not the presented string is in the language. More formally:

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

I P = P S P A C E

, 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.

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 $IP subseteq PSPACE$ , we present a simulation of an interactive proof system by a polynomial space machine. To prove that $PSPACE subseteq IP$ , we show that the PSPACE-complete language TQBF is in IP. Both parts of the proof are adapted from Sipser.

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

p = p (n)

messages. We now construct a machine M that simulates V and is in PSPACE. To do this, we define our machine as follows:

By the definition of

I P

, we have $Pr[V accepts w] ge frac{2}{3}$ if $w in A$ and $Pr[V accepts w] le frac{1}{3}$ if $w not in A$ .

Now, it must be shown that the value can be calculated in polynomial space. Here we take

M j

denote to denote this sequence of messages, $m_1# ldots #m_j$ , exchanged by the prover and the verifier, and we generalize the interaction of V and P to start with an arbitrary message stream

M j

. We take $(V leftrightarrow P)(w,r,M_j) = accept$ if

M j

can be extended with the messages

m j + 1

through

m p

such that:

In other words, when

i

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

r

of length

p

, we define:

$Pr[V leftrightarrow P accepts w starting at M_j] = Pr[(V leftrightarrow P)(w,r,M_j) = accept]$

$Pr[V accepts w starting at M_j] = max_P Pr[V leftrightarrow P accepts w starting at M_j]$

and for every $0 leq j leq p$ and every message history

M j

, we inductively define the function $N_{M_j}$ :

$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}$

where

P r r

is the probability taken over the random string

r

of length

p

. This expression is the average of $N_{M_{j+1}}$ , weighted by the probability that the verifier sent message

m j + 1

Take

M 0

to be the empty message sequence, here we will show that $N_{M_0}$ can be computed in polynomial space, and that $N_{M_0} = Pr[V accepts w]$ . First, to compute $N_{M_0}$ , an algorithm can recursively calculate the values $N_{M_j}$ for every j and

M j

. Since the depth of the recursion is p, only polynomial space is necessary. The second requirement is that we need $N_{M_0} = Pr[V accepts w]$ , the value needed to determine whether w is in A. We use induction to prove this as follows.

We must show that for every $0 leq j leq p$ and every

M j

, $N_{M_j} = Pr[V accepts w starting at M_j]$ , and we will do this using induction on j. The base case is to prove for

j = p

. Then we will use induction to go from p down to 0.

The base case

(j = p)

is fairly simple. Since

m p

is either accept or reject, if

m p

is accept, $N_{M_p}$ is defined to be 1 and Pr[V accepts w starting at

M j

] = 1 since the message stream indicates acceptance, thus the claim is true. If

m p

is reject, the argument is very similar.

For the inductive hypothesis, we assume that for some $j + 1 leq p$ and any message sequence

M j + 1

, $N_{M_{j+1}} = Pr[V accepts w starting at j+1]$ and then prove the hypothesis for

j

and any message sequence

M j

If j is even,

m j + 1

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

If j is odd,

m j + 1

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

$max_{m_{j+1}} Pr[V accepts w starting at M_{j+1}] leq Pr[V accepts w starting at M_j]$

because the prover on the right-hand side could send the message

m j + 1

to maximize the expression on the left-hand side. And:

$max_{m_{j+1}} Pr[V accepts w starting at M_{j+1}] geq Pr[V accepts w starting at M_j]$

Since the same Prover cannot do any better than send that same message. Thus, this holds whether

i

is even or odd and the proof that IP PSPACE is complete.

Here we have constructed a polynomial space machine that uses the best prover

P

for a particular string

w

in language

A

. 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 PSPACE, as desired.

PSPACE is a subset of IP

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

#SAT is a member of IP

$#SAT = { langle phi, k rangle mid phi$ is a cnf-formula with exactly

k

satisfying assignments

}

First we use arithmetization to map the boolean formula with

n

variables,

φ(b 1, b 2,..., b n)

to a polynomial

p φ (x 1, x 2,..., x n)

, where

p φ

mimics

φ

in that

p φ

is 1 if

φ

is true and 0 otherwise provided that the variables of

p φ

are assigned Boolean values. The Boolean operations $vee$ , $wedge$ , and $neg$ used in

φ

are simulated in

p φ

by replacing the operators in

φ

as shown in the table below.

Arithmetization rules for converting a Boolean formula

φ(b 1, b 2,..., b n)

to a polynomial

p φ (x 1, x 2,..., x n)

As an example, $phi = a wedge b vee neg c$ would be converted into a polynomial as follows:

The operations

a b

and

a * b

each result in a polynomial with a degree bounded by the sum of the degrees of the polynomials for

a

and

b

and hence, the degree of any variable is at most the length of

φ

Let

f i

be a function and

F

be a finite field with at least $q le 2^n$ , for $0leq ileq m$ and $a_1, ..., a_iin F$ . Set

f i (a 1,..., a i)

equal to the number of satisfying assignments of

φ

such that each

x j = a j

for $jleq i$ . For $0 leq i leq m$ and for $a_1, ..., a_i in F$ let $f_i(a_1, ..., a_i) = Sigma _{a_{i+1}, ..., a_m in {0, 1}} p(a_1, ..., a_m)$ . Note that the value of

f 0

is still the number of satisfying assignments of

φ

. Also note that

f i

is a univariate function, where the

i t h

element is the variable.

f

, it then sends

q

(along with a short proof of

q

's primality) and

f 0 ()

to the verifier

V

V

checks that

q

is prime and that

f 0 () = k

polynomial in z.

V

verifies that the degree of

f 1

is less than

n

and that

f 0 = f 1 (0) + f 1 (1)

. (If not

V

rejects).

V

now sends a random number

r 1

from

F

P

f 1

is less than

n

and that

f i - 1 (r 1,..., r i - 1) = f i (r 1,..., r i,0) + f i (r 1,..., r i,1)

. (If not

V

rejects).

V

now sends a random number

r i

from

F

P

the value

f m (r 1,..., r m)

. If they are equal

V

accepts, otherwise

V

rejects.

φ

has

k

satisfying assignments, clearly

V

will accept. If

φ

does not have

k

satisfying assignments we assume there is a prover $tilde P$ that tries to convince

V

that

φ

does have

k

satisfying assignments. We show that this can only be done with low probability.

To prevent

V

from rejecting in phase 0, $tilde P$ has to send an incorrect value $tilde f_0()$ to

P

. Then, in phase 1, when

V

chooses a random

r 1

to send to

P

, Pr[ $tilde f_1(r_1) = f_1(r_1)] < n^{-2}$ , for $n geq 10$ . This is because a polynomial in a single variable of degree at most

d

can have no more than

d

roots (unless it always evaluates to 0). So, any two polynomials in a single variable of degree at most

d

can be equal only in

d

places. Since

F > 2 n

the chances of

r 1

being one of these values is at most

n / 2 n

Generalizing this idea for the other phases we have for each $1 leq i leq m$ if $tilde f_{i-1}(r_1, ..., r_{i-1}) not=f_{i-1}(r_1, ..., r_{i-1})$ , then for $n geq 10$ and for

r i

chosen randomly from

F

, Pr[ $tilde f(r_1, ..., r_i) = f_i(r1, ..., r_i)] leq n^{-2}$ . There are

m

phases, so the probability that $tilde P$ is lucky because

V

selects a convenient

r i

is at most

1 / n

. So, no prover can make the verifier accept with probability greater than

1 / n

. We can also see from the definition that the verifier

V

operates in probabilistic polynomial time. Thus, $#SAT in IP$ .

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 IP. The proof technique demonstrated here is credited to Adi Shamir

We know that TQBF is in PSPACE-Complete. So let

ψ

be a quantified boolean expression:

where

φ

is a CNF formula. Then

Q i

is a quantified, either $exists$ or $forall$ . Now

f i

is the same as in the previous proof, but now it also includes quantifiers.

$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}$

Here,

φ(a 1, a 2,..., a i)

φ

with

a 1

a i

substituted for

x 1

x i

. Thus

f 0 ()

is the truth value of

ψ

. In order to arithmetize

ψ

we must add the following identities: $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)$
$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)$

By using the method described in $#SAT$ , we must face a problem that for any

f i

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

ψ = Q 1 x 1 Q 2 x 2 ... Q m x m [φ]

we introduce a new expression:

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

Now for every i $leq$ k we define the function

f i

. We also define

f k (x 1, x 2,.... x m)

to be the polynomial

p (x 1, x 2,... x m)

which is obtained by arithmetizing

φ

. Now in order to keep the degree of the polynomial low, we define

f i

in terms of

f i + 1

$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)$
$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)$
$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)$

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

R x

operation doesn't change the value of the function on boolean inputs. So

f 0

is still the truth value of

ψ

, but the

R x

value produces a result that is linear in x. Also after any

Q i x i

we add $R_{x_1}...R_{x_i}$ in

ψ'

in order to reduce the degree down to 1 after arithmetizing

Q i

.

Now let's describe the protocol. If

n

is the length of

ψ

, all arithmetic operations in the protocol are over a field of size

n 4

where

n

is the length of

ψ

: P sends

f 1 (z)

to V. V uses coefficients to evaluate

f 1 (0)

and

f 1 (1)

. Then it checks that the polynomial is at most

n

and that the following identities are true:

: P sends

f i (r 1, r 2 ... r i - 1, z)

as a polynomial in

z

r 1

denotes the previously set random values for

r 1, r 2 ... r i - 1

V uses coefficients to evaluate

f i (r 1, r 2 ... r i - 1,0)

and

f i (r 1, r 2 ... r i - 1,1)

. Then it checks that the polynomial degree is at most

n

and that the following identities are true:

If either fails then reject.
: V picks a random

r

F

and sends it to P. (If S=R then this

r

replaces the previous

r

).
Goto phase i+1 where P must persuade V that

f i (r 1,..., r)

is correct.

V evaluates

p (r 1, r 2,..., r m)

. Then it checks if

p (r 1, r 2,..., r m) = = f k (r 1, r 2,.... r m)

If they are equal then V accepts, otherwise V rejects.

ψ

is true then V will accept when P follows the protocol. Likewise if is a malicious prover which lies. Then if

ψ

is false, then will need to lie at phase 0 and send some value for

f 0

. So if at phase i, V has an incorrect value for

f i - 1 (r 1,...)

then

f i (r 1,...0)

and

f i (r 1,...1)

must also be incorrect, and so forth. And since the probability for to get lucky on some random

r

is at most the degree of the polynomial divided by the field size:

n / n 4

. The protocol runs through

O (n 2)

phases, so the probability that gets lucky at some phase is . So if is never lucky, then V will reject at phase k+1.

Since we have now shown that both IP PSPACE and PSPACE IP, we can conclude that IP = PSPACE as desired.

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.

External links

Category: Complexity classes In computational complexity theory, a complexity class is a set of problems of related complexity. ... This is a list of complexity classes in computational complexity theory. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In computational complexity theory, co-NP is a complexity class. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In complexity theory, UP (Unambiguous Non-deterministic Polynomial-time) is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input. ... The title given to this article is incorrect due to technical limitations. ... The title given to this article is incorrect due to technical limitations. ... In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In complexity theory, the class NC (Nicks Class) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. ... In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In complexity theory, PSPACE-complete is a complexity class. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. ... PR is the complexity class of all primitive recursive functions â€“ or, equivalently, the set of all formal languages that can be decided by such a function. ... RE (recursively enumerable) is the class of decision problems for which a yes answer can be verified by a Turing machine in a finite amount of time. ... Co-RE is the set of all languages that are complements of a language in RE. In a sense, Co-RE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever. ... RE-complete is the set of decision problems that are complete for the complexity class RE. In a sense, these are the hardest recursively enumerable problems. ... CO-RE-complete is the set of decision problems that are complete for the complexity class co-RE. In a sense, these are the complements of the hardest recursively enumerable problems. ... The class of decision problems solvable by a Turing machine. ... BQP, in computational complexity theory, stands for Bounded error, Quantum, Polynomial time. It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances. ... This article is about the complexity class. ... This article relates to the theory of computation. ... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ... In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has...

Contents

Interactive Proof Systems

Proof that IP = PSPACE

IP is a subset of PSPACE

PSPACE is a subset of IP

#SAT is a member of IP

TQBF is a member of IP

References

External links

Contents

Interactive Proof Systems GA_googleFillSlot("encyclopedia_square");

Proof that IP = PSPACE

IP is a subset of PSPACE

PSPACE is a subset of IP

#SAT is a member of IP

TQBF is a member of IP

References

External links

Interactive Proof Systems