Name
Abstract | ||
|---|---|---|
We show that every language in PSPACE, or equivalently, every language accepted by an unbounded round interactive proof system, ha a 1-round, 2-prover interactive proof system with exponentially small error probability. To obtain this result, we prove the correctness of a simple but powerful method for parallelizing 2-prover interactive proof systems to reduce their error. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/S0022-0000(05)80026-1 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
exponentially small error probability,interactive proof system,powerful method,unbounded round,2-prover interactive proof system,error probability,power method,formal languages,computational complexity | Formal language,Interactive proof system,Computer science,Correctness,Theoretical computer science,Mathematical proof,PSPACE,Probability of error,Proof assistant,Computational complexity theory | Journal |
Volume | Issue | ISSN |
48 | 1 | Journal of Computer and System Sciences |
Citations | PageRank | References |
24 | 8.61 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jin-Yi Cai | 1 | 2327 | 239.71 |
| Anne Condon | 2 | 127 | 28.93 |
| Richard J. Lipton | 3 | 6412 | 1796.57 |