Ip (complexity)

Article Index for Ip

Information About Ip (complexity)

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME
	MORE SHOPPING...

More formally:

wt-avg_{m_{j+1}} N_{M_{j+1}}: j < p\ and\ j\ is\ even\
\end{cases}


where the term $wt-avg\_\{m\_\{j+1\}\}N\_\{M\_\{j+1\}\}$ is defined as follows:

$wt-avg\_\{m\_\{j+1\}\}N\_\{M\_\{j+1\}\}\; =\; \backslash sum\_\{m\_\{j+1\}\}(Pr\_r${Link without Title} )

where $Pr\_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\}\; =\; Praccepts\backslash \; 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\}\; =\; Praccepts\; 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\; \backslash leq\; j\; \backslash leq\; p$ and every $M\_j$, $N\_\{M\_j\}\; =\; Praccepts\backslash \; w\backslash \; starting\backslash \; 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 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\; \backslash leq\; p$ and any message sequence $M\_\{j+1\}$, $N\_\{M\_\{j+1\}\}\; =\; Praccepts\backslash \; w\backslash \; starting\backslash \; at\backslash \; j+1$ and then prove the hypothesis for $j$ and any message sequence $M\_j$.

• Pr accepts\ w\ starting\ at\ M_{j+1} ). Finally, by definition, we can see that this is equal to $Praccepts\backslash \; w\backslash \; starting\backslash \; at\backslash \; M\_j$.

• Pr accepts\ w\ starting\ at\ M_{j+1} . This is equal to $Praccepts\backslash \; w\backslash \; starting\backslash \; at\backslash \; M\_j$ since:

$max\_\{m\_\{j+1\}\}\; Praccepts\backslash \; w\backslash \; starting\backslash \; at\backslash \; M\_\{j+1\}\backslash leq\; Praccepts\backslash \; w\backslash \; starting\backslash \; at\backslash \; 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\}\}\; Praccepts\backslash \; w\backslash \; starting\backslash \; at\backslash \; M\_\{j+1\}\backslash geq\; Praccepts\backslash \; w\backslash \; starting\backslash \; at\backslash \; 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 $\backslash subseteq$ '''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 input bits in polynomial space.
Since we have simulated an interactive proof system with a polynomial space machine, we have shown that IP $\backslash subseteq$ '''PSPACE''', as desired.


$\backslash Box$


PSPACE is a subset of IP


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


#SAT is a member of IP

We begin by showing that $\backslash \#SAT\; \backslash in\; IP$, where:


$\backslash \#SAT\; =\; \backslash \{\; \backslash langle\; \backslash phi,\; k\; angle\; \backslash mid\; \backslash phi$ is a cnf-formula with exactly $k$ satisfying assignments $\backslash \}$.


Note that this is different from the normal definition of #SAT , in that it is a decision problem, rather than a function.

First we use arithmetization to map the boolean formula with $n$ variables, $\backslash phi(b\_1,\; b\_2,\; ...,\; b\_n)$ to a polynomial $p\_\backslash phi(x\_1,\; x\_2,\; ...,\; x\_n)$, where $p\_\backslash phi$ mimics $\backslash phi$ in that $p\_\backslash phi$ is 1 if $\backslash phi$ is true and 0 otherwise provided that the variables of $p\_\backslash phi$ are assigned Boolean values. The Boolean operations , $\backslash wedge$, and $$
eg used in $\backslash phi$ are simulated in $p\_\backslash phi$ by replacing the operators in $\backslash phi$ as shown in the table below.

As an example,
eg c would be converted into a polynomial as follows:

eg c

• $p\_\backslash phi\; =\; a\; \backslash wedge\; (1\; -\; (1-b)(1-(1-c)))$


• $p\_\backslash phi\; =\; a\; (1\; -\; (1-b)c)$


• $p\_\backslash phi\; =\; a\; -\; (ac-abc)$

• 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 $\backslash phi$.

Now let $F$ be a finite field with order $q\; >\; 2^n$; also demand that q be at least 1000. For each $0\backslash leq\; i\backslash leq\; n$, define a function $f\_i$ on F, having parameters $a\_1,\; ...,\; a\_\{i-1\}\backslash in\; F$, and a single variable $a\_i\backslash in\; F$: For $0\; \backslash leq\; i\; \backslash leq\; n$ and for $a\_1,\; ...,\; a\_i\; \backslash in\; F$ let $f\_i(a\_1,\; ...,\; a\_i)\; =\; \backslash Sigma\; \_\{a\_\{i+1\},\; ...,\; a\_n\; \backslash in\; \backslash \{0,\; 1\backslash \}\}\; p(a\_1,\; ...,\; a\_n)$. Note that the value of $f\_0$ is the number of satisfying assignments of $\backslash phi$. $f\_0$ is a void function, with no variables.

Now the protocol for $\backslash \#SAT$ works as follows:

• Phase 0:
  The prover $P$ choses a prime $q\; >\; 2^n$ and computes $f$, it then sends $q$ and $f\_0()$ to the verifier $V$. $V$ checks that $q$ is a prime greater than $max(1000,\; 2^n)$ and that $f\_0()\; =\; k$.


• Phase 1:
  $P$ sends the coefficients of $f\_1(z)$ as a 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$ to $P$.


• Phase i:
  $P$ sends the coefficients of $f\_i(r\_1,\; ...,\; r\_\{i-1\},\; z)$ as a polynomial in $z$. $V$ verifies that the degree of $f\_i$ is less than $n$ and that $f\_\{i-1\}(r\_1,\; ...,\; r\_\{i-1\})\; =\; f\_i(r\_1,\; ...,\; r\_\{i-1\},\; 0)\; +\; f\_i(r\_1,\; ...,\; r\_\{i-1\},\; 1)$. (If not $V$ rejects). $V$ now sends a random number $r\_i$ from $F$ to $P$.


• Phase n+1:
  $V$ evaluates $p(r\_1,\; ...,\; r\_n)$ to compare to the value $f\_n(r\_1,\; ...,\; r\_n)$. If they are equal $V$ accepts, otherwise $V$ rejects.

Note that this is a public-coin algorithm.

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