On Completeness and Soundness in Interactive Proof Systems.
Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos · 1989
An interactive proof system with Perfect Completeness (resp. Perfect Soundness) for a language L is an interactive proof (for L) in which for every x 2 L (resp. x 62 L) the verifier always accepts (resp. always rejects). We show that any language having an interactive proof system has one (of the Arthur-Merlin type) with perfect completeness. On the other hand, only languages in NP have interactive proofs with perfect soundness. Work done while third author was working at the IBM-Scientific Center, Technion City, Haifa, Israel. Second author was partially supported by the Fund for Basic Research Administered by the Israeli Academy of Sciences and Humanities. Fifth author was partially supported by PSC-CUNY grant. Appeared in Advances in Computing Research: A Research Annual, Vol. 5 (Randomness and Computation, S. Micali, ed.), pages 429--442, 1989. Warning: Reproduced almost automatically from an old troff file. The resulting text was not proofread. Updated affiliation for Oded Gold...