On the Power of Multi-Prover Interactive Protocols
On the Power of Multi-Prover Interactive Protocols
复制标题
DOI：
10.1016/0304-3975(94)90251-8
复制
发表时间：
1994-11
期刊：
影响因子：
--
通讯作者：
L. Fortnow;John Rompel;M. Sipser
中科院分区：
文献类型：
--
作者：
L. Fortnow;John Rompel;M. Sipser
我们将研究具有相互分离的多个证明者的交互式证明系统的复杂性问题。这个模型是由Ben-Or等人（1988）开发的，它允许验证者与证明者相互博弈。我们将此模型与使用oracle作为证明者的另一种交互式证明系统模型等效。我们还表明，这些模型所接受的每种语言都存在于不确定的指数时间中。我们展示了一个相对化的世界，其中co-NP语言没有多个证明者交互证明。最后，我们展示了一个简单的示例，说明不能像单个证明者模型那样容易地并行处理多个证明者协议。
We look at complexity issues of interactive proof systems with multiple provers separated from each other. This model, developed by Ben-Or et al. (1988) allows the verifier to play the provers off each other. We show this model equivalent to an alternative interactive proof system model using oracles as provers. We also show that every language accepted by these models lies in nondeterministic exponential time. We exhibit a relativized world where a co-NP language does not have multiple prover interactive proofs. Finally, we show a simple example that one cannot parallelize multiple prover protocols as easily as the single prover model.