Adi Shamir
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.
- 1 ~BABAI, L. Trading group theory for randomness. In Proceedings of &e 17th ACM Syrnposiztm ~on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 421-429. Google Scholar
- 2 ~BEAVER, D., AND FEIGENBAUM, J. Hiding instances in multioracle queries. In Proceedzngs of ~the 7th Annual Symposium on Theorettcal Aspects of Computer Science. Springer-Verlag, New ~York, 1990, pp. 37-48. Google Scholar
- 3 ~BOPPANA, R., HASTAD, J., AND ZACHOS, S. Does co-NP have short interactive proofs? Inf. ~Proc. Lett. 25 (1987), 127-132. Google Scholar
- 4 ~FORTNOW, L., AND StPSER, M. Interactive proof systems with a log space verifier. Unpub- ~lished manuscript, 1988.Google Scholar
- 5 ~GAREY, M., AND JOHNSON, D. Computers and intractability, A guide to the theory of ~NP-completeness. W. H. Freeman, San Francisco, Calif. 1979. Google Scholar
- 6 ~GOLDREICH, O., MICALI, S., AND WIGDERSON, m. Proofs that yield nothing but the validity of ~the assertion and a methodology of cryptographic protocol design. In Proceedings of 27th ~ Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 174-187.Google Scholar
- 7 ~GOLDWASSER, S., AND SIPSER, M. Private coins versus public coins in interactive proof ~systems. In Proceedings of the 18th Annual ACM Syrnpostum on Theory of Computing (Berke- ~ley, Calif., May 28-30). ACM, New York, 1986, pp. 59-68. Google Scholar
- 8 ~GOLDWASSER, S., MICALI, S., AND RACKOFF, C. The knowledge complexity of interactive ~proof-systems. In Proceedings of 17th Annual ACM Symposium on Theory of Computing ~(Providence, R.I., May 6-8). ACM, New York, 1985, pp. 291-304. Google Scholar
- 9 ~LIPTON, R. New directions in testing. Unpublished manuscript, 1989.Google Scholar
- 10 ~LUND, C., FORTNOW, L., KARLOFF, H., AND NISAN, N. Algebraic methods for interactive ~proof systems. In Proceedings of 31st Symposium on Fottndations of Computer Science. {EEE, ~New York, 1990, pp. 2-90.Google Scholar
- 11 ~TODA, S. On the computational power of PP and ~ P. In Proceedings of 30th Symposium on ~Foundations of Computer Science. IEEE, New York, 1989, pp. 514-519.Google Scholar
- 12 ~VALIANT, L. The complexity of computing the permanent. Theoret. Comput. Sci. 8 (1979), ~189-201.Google Scholar
Index Terms
- IP = PSPACE
Recommendations
IP = SPACE: simplified proof
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.
The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
In 1990, PSPACE was shown to be identical to IP, the class of languages with interactive proofs [18,20]. Recently, PSPACE was again recharacterized, this time in terms of (Random) Probabilistically Checkable Debate Systems [7,8]. In particular, it was ...
Algebraic dependencies and PSPACE algorithms in approximative complexity
CCC '18: Proceedings of the 33rd Computational Complexity ConferenceTesting whether a set f of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, ...
Comments