Interactive proof systems: Provers that never fail and random selection
Interactive proof systems: Provers that never fail and random selection
复制标题
交互式证明系统：永不失败的证明和随机选择
DOI：
10.1109/sfcs.1987.35
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
M. Sipser
中科院分区：
文献类型：
--
作者：
Oded Goldreich;Y. Mansour;M. Sipser
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 ∈ L (resp. x ∉ L) the verifier always accepts (resp. always rejects). Zachos and Fuerer showed that any language having a bounded interactive proof has one with perfect completeness. We extend their result and show that any language having a (possibly unbounded) interactive proof system has one with perfect completeness. On the other hand, only languages in NP have interactive proofs with perfect soundness. We present two proofs of the main result. One proof extends Lautemann's proof that BPP is in the polynomial-time hierarchy. The other proof, uses a new protocol for proving approximately lower bounds and "random selection". The problem of random selection consists of a verifier selecting at random, with uniform probability distribution, an element from an arbitrary set held by the prover. Previous protocols known for approximate lower bound do not solve the random selection problem. Interestingly, random selection can be implemented by an unbounded Arthur-Merlin game but can not be implemented by a two-iteration game.
利用阳光进行光合作用的研究成果报告（1986）。
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--