Can anyone give an intuitive explanation to why IP = PSPACE, or at least one direction of it?
I looked at many research papers but its very hard to understand the formalism unless you have a solid background in Turing machines and complexity theory. I'm an undergraduate.
I found it most easy to understand according to reference here for undergrad level:
It's easy to show that IP $\subseteq$ PSPACE . Suppose L ∈ IP . Then we have some verifier V for L. The PSPACE algorithm we use to decide L is to compute z = max Pr[V ↔ P accepts w] . By the definition of IP , if z ≥ 2/3 , then we know that w ∈ L. If z ≤ 1/3 , then we know that w !∈ L. Note that if V is a verifier for L, 1/3 < z < 2/3 will never occur.
Now we need to show that it's possible to compute z in PSPACE. Suppose V runs in p(n) steps, where n = |w|. Then any given response by P is no longer than p(n). Also, V chooses at most p(n) random numbers. We may recursively simulate V while branching for each random number, and each possible response by P. Therefore, the recursion depth is polynomial, so we can perform such a recursion in PSPACE. We keep a count of the accepting branches produced by P's optimal responses, as well as the total number of branches. These numbers will be exponential in n, but the length of the numerical representation is polynomial in n. The ratio computed by this PSPACE algorithm is z, therefore IP $\subseteq$ PSPACE.
Another related intuition is imagine a limit case where a subset of IP is the deterministic Interactive Proof class, which is similar to IP but has a deterministic verifier. This class is equal to NP and thus we can kind of intuited this subset of IP = NP $\subseteq$ PSPACE. The other direction, however, is much harder from the same reference:
Recall that TQBF, the language of true quantified boolean formulas, is PSPACE-complete. Therefore, PSPACE ⇔ TQBF ∈ IP. The goal of this paper will be to show TQBF ∈ IP, hence IP = PSPACE...
I'm no expert here, hope this will be somewhat helpful.
