IP = SPACE

Alexander Shen · Journal of the ACM · 1992

Lund et al. [1] have proved that PH is contained in IP. Shamir [2] improved this technique and proved that PSPACE = IP. In this note, a slightly simplified version of Shamir's proof is presented, using degree reductions instead of simple QBFs.

Read the paper · More papers on PaperTik