IP=PSPACE

It is proved 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. The interactive proofs introduced use only public coins, are accepted with probability one when the prover is honest, require only logarithmic workspace when the verifier is given a two-way access to his or her random tape, and by the use of known techniques can be turned into zero-knowledge proofs under the sole assumption that one-way functions exist. >

Authors

• Adi Shamir

Keywords

• Polynomials
• Mathematics
• Boolean functions
• Point Of Use
• Boolean Variable
• Free Variables
• Boolean Function
• Universal Quantifier
• Negation
• Functional Form
• Polynomial Of Degree
• Turing Machine
• Negligible Probability