![](https://csdnimg.cn/release/download_crawler_static/88777922/bg7.jpg)
相比之下,所有其他已知的证明[JJUW11,Wu10]都依赖于这样一个事实,即可以假设验证者
只与证明者交换三条消息[KW 00]。Jain等人的原始证明[JJUW11]还依赖于另外一个事实,即验证
者给证明者的唯一消息可能只是一个经典的抛硬币
[MW05]
。
当然,每一个其他的竞争证明复杂性类,其协议可以被转换为双重交互证明,也崩溃到
PSPACE
,例如前面提到的基于短量子博弈的类
DQIP
(
1
,
2
)
从DQIP和DIP到PSPACE的崩溃可以看出,这些类在完备下是封闭的,并且它们对于参数
c
,
s
的选择是鲁棒的。(实际上,可以假设对于任何期望的多项式有界函数
q
(
x
),
c = 1
且
s2
−q--
见
6.3
节。)
在本工作之前,多项式空间算法仅已知用于两圈经典的间
具有竞争证明者的主动证明(RG(2))、具有竞争证明者的单轮量子交互证明(QRG(1))以
及单证明者量子交互证明(
QIP
)。我们的结果统一和归纳了所有这些算法
.
它还表明了第一次存
在的多项式空间算法的竞争,证明者相互作用(经典或量子),其中一个证明者的反应自适应其
他。
最后,我们的研究结果说明了一个不同的效果之间的公共随机
性单
证明者交互式证明和
竞争
证
明者交互式证明。 任何具有单个证明者的经典交互式证明都可以通过另一个
公共硬币
交互式证明
来模拟,其中验证者发送给证明者的消息完全由均匀随机位组成,并且验证者不使用其他随机性
[GS 89]
。将公共币交互的概念扩展到竞争证明者交互,很容易看出,与公共币验证者的任何此类
交互都可以通过双重交互证明来模拟
[3
]因此,RG的公共硬币版本是DIP的子集,我们现在知道DIP
等于
PSPACE
。因此,与公共币
IP
=
IP
的单一证明者情况相比,在竞争证明者情况下,我们建立以
下内容。
推论
2.4
。
public-coin-RG
/
= RG
除非
PSPACE = EXP
。
1.4
技术概述
1.4.1
矩阵乘性权值更新法
定理
1
的证明中给出的并行预言算法是文献
[1]
中提出的
矩阵乘权更新方法(
MMW
)
的一个例子。
[AHK05、WK06、Kal07]。我们借鉴了最近应用这种方法并行算法的量子复杂性类[JW 09,
JUW09
,
JJUW11
,
Wu10]
的宝贵经验。我们还广泛使用高效的并行算法进行各种矩阵操作任务,
如计算矩阵的奇异值分解或指数 读者是指冯祖尔Gathen更多的细节并行算法矩阵运算[vzG93]和工
程的Jain
等人。
用于讨论这些算法在矩阵乘法权重更新方法的并行实现中的使用 [JUW09,
JJUW11]。
在其不变的形式下,
MMW
可用于求解
密度算子
-
半正定矩阵
X
上的极小极大问题,
其中
Tr
(
X
)
=
1。我们引入了一个新的扩展,这种方法的最小最大问题的定义在
SDP
(
1
)的区域A
-
一个域的
k-
元组的密度算子
躺在一个
严格的子空间
的仿射空间与
k-
元组的密度算子。我们的方
法的高级方法如下:
3
证明草图:
由于验证者