IP = PSPACE
Journal of the ACMPublished 1 October 1992Open access
Adi Shamir
Citations657
SJR quartileQ1
SJR score2.25
SNIP3.16
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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 could be generated with polynometric space.
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
Computer Science
Theoretical Computer ScienceThe complexity of computing the permanent
2,759 Citations1979Leslie G. Valiant
It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations.
The knowledge complexity of interactive proof-systems
1,212 Citations1985Sbafi Goldwasser, Silvio Micali +1 more
Trading group theory for randomness
772 Citations1985László Babai
The aim of this paper is to replace most of the (proven and unproven) group theory of [BS] by elementary combinatorial arguments and defines a new hierarchy of complexity classes “just above NP</italic””, introducing Arthur vs. Merlin games and proving that it consists precisely of those languages which belong to NP.
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
544 Citations1986Oded Goldreich, Silvio Micali +1 more
This paper demonstrates the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff that efficiently demonstrate membership in the language without conveying any additional knowledge.
Private coins versus public coins in interactive proof systems
393 Citations1986S. Goldwasser, M. Sipser
The probabilistic, nondeterministic, polynomial time Turing machine is defined and shown to be equivalent in power to the interactive proof system and to BPP much as BPP is the Probabilistic analog to P.
Information Processing LettersDoes co-NP have short interactive proofs?
367 Citations1987Ravi B. Boppana, Johan Håstad +1 more
It is proved that if the complexity class co -NP is contained in IP[k] for some constant k, then the polynomial-time hierarchy collapses to the second level and if the Graph Isomorphism problem is NP-complete, then this hierarchy collapses.
Lecture notes in computer scienceHiding instances in multioracle queries
239 Citations1990Donald Beaver, Joan Feigenbaum
It is shown that, if f is an NP-hard function, A cannot query a single oracle B while hiding all but the size of the instance, assuming that the polynomial hierarchy does not collapse.
On the computational power of PP and (+)P
233 Citations1989Seinosuke Toda
It follows that neither PP nor (+)P is a subset of or equivalent to PH unless PH collapses to a finite level, strong evidence that both classes are strictly harder than PH.
Algebraic methods for interactive proof systems
190 Citations2002Carsten Lund, Lance Fortnow +2 more