1.Previous
3.Next

IP ? PSPACE and PSPACE ? IP.

IP ? PSPACE

In order to demonstrate that IP ? PSPACE, we present a simulation of an interactive proof system by a polynomial space machine. Now, we can define:

:

and for every 0 <= j <= p and every message history M_j, we inductively define the function N_Mj:

:

where:

:

where Pr_r is the probability taken over the random string r of length p. This

1.Previous
3.Next