On the success probability of the two provers in one-round proof systems
On the success probability of the two provers in one-round proof systems
复制标题
关于一轮证明系统中两个证明者的成功概率
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
U. Feige
中科院分区：
文献类型：
--
作者：
U. Feige
作者探讨了在不增加证明者数量或轮数的情况下降低双证明者一轮证明系统错误概率的问题。构建了一个示例，即非交互式协议，其中并行执行该协议两次根本不会降低错误概率。证明了特定类协议错误概率的上界。作为一个推论，表明每个NEXPTIME语言都具有一个具有恒定错误概率的一轮双证明者证明系统。
The author addresses the problem of reducing the error probability of two-prover one-round proof systems, without increasing the number of provers or the number of rounds. An example, the noninteractive agreement protocol, where executing such a protocol twice in parallel does not decrease the error probability at all is constructed. Upper bounds on the error probability of specific classes of protocols are proved. As a corollary, it is shown that every NEXPTIME language has a one-round two-prover proof system with constant error probability.<<ETX>>