IP = PSPACE
- 1 October 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 39 (4), 869-877
- https://doi.org/10.1145/146585.146609
Abstract
In this paper, it is proven that when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated with polynomial space.Keywords
This publication has 2 references indexed in Scilit:
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- The complexity of computing the permanentTheoretical Computer Science, 1979