Next: A Trade-off between Information
Up: The Technion Period (1986-94)
Previous: How to Solve any
It is shown that any interactive proof can be transformed into
one with perfect completeness. In contrast, perfectly sound
interactive proofs exist only for NP.
Comments:
Authored by M. Furer, O. Goldreich, Y. Mansour, M. Sipser and S. Zachos. Appeared in
- Proc. of the 28th FOCS, pp. 449-461, 1987.
- Advances
in Computing Research: a research annual,
Vol. 5 (Randomness and Computation, S. Micali, ed.),
pp. 429-442, 1989.
Oded Goldreich
2003-07-30