IP = PSPACE

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

IP = PSPACE

Full text

Pdf (561 KB)

Source

Journal of the ACM (JACM) archive
Volume 39 , Issue 4 (October 1992) table of contents

Pages: 869 - 877

Year of Publication: 1992

ISSN:0004-5411

Author

Adi Shamir

The Weizmann Institute of Science, Rehovot, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 186, Citation Count: 60

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/146585.146609 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	2	Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
	3	R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
	4	~FORTNOW, L., AND StPSER, M. Interactive proof systems with a log space verifier. Unpub- ~lished manuscript, 1988.
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	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.
	7	S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
	8	S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
	9	~LIPTON, R. New directions in testing. Unpublished manuscript, 1989.
	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.
	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.
	12	~VALIANT, L. The complexity of computing the permanent. Theoret. Comput. Sci. 8 (1979), ~189-201.

CITED BY 60

	Juris Hartmanis, On computational complexity and the nature of computer science, ACM Computing Surveys (CSUR), v.27 n.1, p.7-16, March 1995
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States
	Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States
	Adam R. Klivans , Daniel Spielman, Randomness efficient identity testing of multivariate polynomials, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.216-223, July 2001, Hersonissos, Greece
	Uriel Feige , Joe Kilian, Making games short (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.506-516, May 04-06, 1997, El Paso, Texas, United States
	Giovanni Di Crescenzo , Kouichi Sakurai , Moti Yung, On zero-knowledge proofs (extended abstract): “from membership to decision”, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.255-264, May 21-23, 2000, Portland, Oregon, United States
	Richard Lipton , Nisheeth Vishnoi, Deterministic identity testing for multivariate polynomials, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Salil Vadhan, On transformation of interactive proofs that preserve the prover's complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.200-207, May 21-23, 2000, Portland, Oregon, United States
	Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996
	Manuel Blum , Sampath Kannan, Designing programs that check their work, Journal of the ACM (JACM), v.42 n.1, p.269-291, Jan. 1995
	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998
	A. Shen, IP = SPACE: simplified proof, Journal of the ACM (JACM), v.39 n.4, p.878-880, Oct. 1992
	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998
	Michael Sipser, The history and status of the P versus NP question, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.603-618, May 04-06, 1992, Victoria, British Columbia, Canada
	Daphne Koller , Nimrod Megiddo , Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.750-759, May 23-25, 1994, Montreal, Quebec, Canada
	Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001
	Juris Hartmanis, Turing Award lecture on computational complexity and the nature of computer science, Communications of the ACM, v.37 n.10, p.37-43, Oct. 1994
	Lance Fortnow , Michael Sipser, Retraction of probabilistic computation and linear time, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.750, May 04-06, 1997, El Paso, Texas, United States
	Alexei Kitaev , John Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.608-617, May 21-23, 2000, Portland, Oregon, United States
	Anne Condon , Joan Feigenbaum , Carsten Lund , Peter Shor, Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.305-314, May 16-18, 1993, San Diego, California, United States
	Richard Beigel , Harry Buhrman , Lance Fortnow, NP might not be as easy as detecting unique solutions, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.203-208, May 24-26, 1998, Dallas, Texas, United States
	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998
	Jörg Rothe, Some facets of complexity theory and cryptography: A five-lecture tutorial, ACM Computing Surveys (CSUR), v.34 n.4, p.504-549, December 2002
	Hirotada Kobayashi , Keiji Matsumoto, Quantum multi-prover interactive proof systems with limited prior entanglement, Journal of Computer and System Sciences, v.66 n.3, p.429-450, May 2003
	Oded Goldreich , Salil Vadhan , Avi Wigderson, On interactive proofs with a laconic prover, Computational Complexity, v.11 n.1/2, p.1-53, January 2003
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate PCPs, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.41-50, May 01-04, 1999, Atlanta, Georgia, United States
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Amit Sahai , Salil Vadhan, A complete problem for statistical zero knowledge, Journal of the ACM (JACM), v.50 n.2, p.196-249, March 2003
	Lance Fortnow, Beyond NP: the work and legacy of Larry Stockmeyer, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Lance Fortnow, One complexity theorist's view of quantum computing, Theoretical Computer Science, v.292 n.3, p.597-610, 31 January 2003
	Phillip G. Bradford , Michael Wollowski, A formalization of the Turing test, ACM SIGART Bulletin, v.6 n.4, p.3-10, Oct. 1995
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, January 2004
	John Watrous, PSPACE has constant-round quantum interactive proof systems, Theoretical Computer Science, v.292 n.3, p.575-588, 31 January 2003
	John M. Hitchcock, Hausdorff dimension and oracle constructions, Theoretical Computer Science, v.355 n.3, p.382-388, 14 April 2006
	Jin-Yi Cai , Hong Zhu, Progress in computational complexity theory, Journal of Computer Science and Technology, v.20 n.6, p.735-750, November 2005
	Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity Via Uniform Reductions, Computational Complexity, v.16 n.4, p.331-364, December 2007
	Scott Aaronson , Avi Wigderson, Algebrization: a new barrier in complexity theory, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Markus Bläser , Moritz Hardt , Richard J. Lipton , Nisheeth K. Vishnoi, Deterministically testing sparse polynomial identities of unbounded degree, Information Processing Letters, v.109 n.3, p.187-192, January, 2009
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007
	Juris Hartmanis, Turing award lecture: on computational complexity and the nature of computer science, ACM Turing award lectures, ACM, New York, NY, 2007
	David S. Johnson, The NP-completeness column: Finding needles in haystacks, ACM Transactions on Algorithms (TALG), v.3 n.2, p.24-es, May 2007
	A. Pavan , Alan L. Selman , Samik Sengupta , N. V. Vinodchandran, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Theoretical Computer Science, v.385 n.1-3, p.167-178, October, 2007
	Rahul Santhanam, Circuit lower bounds for Merlin-Arthur classes, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Lane A. Hemaspaandra, SIGACT news complexity theory column 52, ACM SIGACT News, v.37 n.3, September 2006
	Lenore Cowen , Joan Feigenbaum , Sampath Kannan, A formal framework for evaluating heuristic programs, Annals of Mathematics and Artificial Intelligence, v.22 n.3-4, p.193-206, 1998
	Yasuyuki Tsukada, Interactive and Probabilistic Proof of Mobile Code Safety, Automated Software Engineering, v.12 n.2, p.237-257, April 2005
	Anne Condon, Approximate solutions to problems in PSPACE, ACM SIGACT News, v.26 n.2, p.4-13, June 1995
	Oded Goldreich, Probabilistic Proof Systems: A Primer, Foundations and Trends® in Theoretical Computer Science, v.3 n.1, p.1-91, January 2008
	Brendan Juba , Madhu Sudan, Universal semantic communication I, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Shafi Goldwasser , Yael Tauman Kalai , Guy N. Rothblum, Delegating computation: interactive proofs for muggles, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Madhu Sudan, Probabilistically checkable proofs, Communications of the ACM, v.52 n.3, March 2009
	Harumichi Nishimura , Tomoyuki Yamakami, An application of quantum finite automata to interactive proof systems, Journal of Computer and System Sciences, v.75 n.4, p.255-269, June, 2009
	Scott Aaronson , Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, ACM Transactions on Computation Theory (TOCT), v.1 n.1, p.1-54, February 2009
	Shingo Hasegawa , Shuji Isobe , Hiroki Shizuya, NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.342-344, January 2008
	Russell Impagliazzo , Valentine Kabanets , Antonina Kolokolova, An axiomatic approach to algebrization, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Christopher Lusena , Judy Goldsmith , Martin Mundhenk, Nonapproximability results for partially observable Markov decision processes, Journal of Artificial Intelligence Research, v.14 n.1, p.83-103, January 2001