Journal of the ACM · 1992 · 657 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationDeductive VerificationInteractive Proof SystemsProof ComplexityRandomized AlgorithmsRandomized ComplexityRandomized ComputationPolynomial SpacePolynomial Time ComplexityPolynomial-time AlgorithmsRandomized Complexity TheoryRandomized Proof Systems
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.
8
The complexity of computing the permanent
Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations
The knowledge complexity of interactive proof-systems
Sbafi Goldwasser, Silvio Micali, Charles Rackoff · 1985 · 1.2K citations · Full text
Trading group theory for randomness
László Babai · 1985 · 782 citations
Private coins versus public coins in interactive proof systems
S. Goldwasser, M. Sipser · 1986 · 398 citations