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
PSPACEMathematical proofPolynomialMathematicsComputer scienceDiscrete mathematicsTime complexityCombinatoricsComputational complexity theoryAlgorithmGeometryMathematical analysis
Affiliated Institutions
Related Publications
Quantum circuit complexity
We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a qua...
On the Power of Quantum Computation
The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on...
The quantum challenge to structural complexity theory
A nontechnical survey of recent quantum-mechanical discoveries that challenge generally accepted complexity-theoretic versions of the Church-Turing thesis is presented. In parti...
Computational Sample Complexity
In a variety of PAC learning models, a trade-off between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrict...
On the power of quantum computation
The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum me...
Publication Info
- Year
- 1992
- Type
- article
- Volume
- 39
- Issue
- 4
- Pages
- 869-877
- Citations
- 638
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
638
OpenAlex
Cite This
Adi Shamir
(1992).
IP = PSPACE.
Journal of the ACM
, 39
(4)
, 869-877.
https://doi.org/10.1145/146585.146609
Identifiers
- DOI
- 10.1145/146585.146609