Towards a Doubly Efficient IP=PSPACE

Liyan Chen, Matthew M. Hong, Yael Tauman Kalai +1

We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynom…