没有合适的资源?快使用搜索试试~ 我知道了~
首页并行逼近极大极小问题算法:竞争证明复杂性的突破
并行逼近极大极小问题算法:竞争证明复杂性的突破
0 下载量 199 浏览量
更新于2024-06-17
收藏 832KB PDF 举报
本文主要探讨了一种针对极大极小问题的有效并行逼近算法,该算法源自矩阵乘法权重更新方法,特别适用于求解经典或量子环境中的竞争性两方策略。作者们在加拿大多伦多滑铁卢大学量子计算研究所和计算机科学学院的Gus Gutoski和晓迪,以及美国密歇根大学电气工程与计算机科学系的研究人员,提出了这一创新性解决方案。 极大极小问题通常涉及在一个约束条件下找到最优化的决策,如在半定规划(SDP)框架中,目标是寻找一组矩阵X1到Xk,使得Tr(XkP)最小,同时满足一系列线性等式和矩阵非负性条件。在这个背景下,文章关注的是如何在并行环境下更高效地解决这类问题,特别是当裁判允许双方自由交换消息时。 新提出的并行逼近算法允许裁判与一方交换无限次消息,而后续一方还可以与其他任意数量的额外消息进行交互。这种设计使得算法能够处理更为复杂的互动情况,首次展示了存在一种适应性反应的并行解决方案。通过证明这些竞争证明复杂性类,如QRG(2),SQG和新定义的DIP和DQIP,研究者揭示了这些类与PSPACE复杂性类的关系,表明它们可能被包含在PSPACE内。 其中一个关键的应用案例是半定规划的并行逼近方案,其中可行域由满足转录一致性条件的半定矩阵列表构成。将这个特殊情形应用于多消息量子交互式证明中,研究人员得以获得一个直接的多项式空间模拟,从而为QIP=PSPACE的原始证明提供了一个新的基础。 这项工作不仅提升了极大极小问题的并行求解能力,而且深化了我们对量子计算和经典计算下交互式证明复杂性的理解。这一突破性成果对于推动理论计算机科学,特别是在量子博弈论、优化算法和复杂性理论领域,具有重要的理论价值和实践意义。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/88790138/bg6.jpg)
6
⊆
2
⊆
[FK97]
,得到特征
RG
=
EXP
。这在
Ref
中得到了证实
[2017 - 07 - 07 00
:
07
:
07]
这是一个人,
QRG = RG = EXP
,
这是著名的折叠
QIP = IP = PSPACE
的竞争证明者版本,用于单证明者交互式证明
[LFKN92
,
Sha92
,
JJUW11]
。
对于有界转向类,
Fortnow
等人的结果。
告诉我们RG(1)本质上是
SP
[FIKU08]
的随机化版
本。
Feige
和
Kilian
证明了
RG
(
2
)
=
PSPACE
[FK97]
。
2
对于有界圈量子类,
[JW 09]
证明了
QRG
(1) PSPACE。QRG(2)的复杂性是
[JJUW11]
的一个公开问题,本
文解决了这个问题。
RG
(
k
)和
QRG
(
k
)对于所有其他
k
的精确复杂度是未知的。有界回合双
量子交互式证明以前曾在
短量子博弈
的名称下进行过研究
;
相关的复杂性类被称为SQG。为了
统一符号,让
DQIP
(
k
,
l
)表示由允许与竞争证明者进行双量子交互证明的问题组成的类,
其中验证者与是证明者交换不超过
k
个消息,然后与非证明者交换不超过
l
个消息SQG类首先在
Ref.[GW 05]
等于
DQIP
(
1
,
2
),其中示出了该类包含
QIP
=
DQIP
(
poly
,
0
)。短量子博弈
的重要性已经被
QIP = PSPACE
的证明所削弱,因为
QIP
的包容性不再是这样一个特殊的属
性。然而,PSPACE包含在DQIP(1
,
2)中仍然是有趣的,因为不知道PSPACE是否包含在DIP
(
1
,
2
)中,
DIP
(
1
,
2
)是这个的经典版本。
课
1.3.3
我们的贡献
正如我们在第
5
节中所解释的,定理
1
的预言机算法
--
以及适当选择的预言机的并行实现
--
意味着在
双量子交互式证明中,证明者的近最优策略然后,下面的遏制来自一个标准论点(在5.4节中总
结)。
定理
2.
DQIP空间
。
这种包容性,当与平凡的包容性
IP<$DIP<$DQIP
和众所周知的事实,即
PSPACE<$
IP[LFKN
92
,
Sha 92]
相结合时,产生以下特征。
推论
2.1
。
DQIP = DIP = PSPACE
。
作为推论2.1的一个特例,我们得到了[JJUW11]的一个公开问题的解
推论2.2。QRG(2)
=
PSPACE
。
我们的结果的另一个特殊情况是多消息量子交互证明的直接多项式空间模拟,导致
QIP
=
PSPACE的第一性原理证明。
推论
2.3
。 QIP
=
PSPACE
通过多消息量子交互证明的直接多项式空间模拟。
[2
]我们称之为RG(2)的类被Feige和Kilian称为RG(1)[FK 97]。这种符号上的冲突源于这样一个事实,即我们
轮流
测量交互的长度(
即
每个证明者的消息),而那些作者则以消息的
轮数来
测量交互。 这种符号的转换是由
Jain
和
Watrous
发起的,他们需要一个方便的符号来进行一轮互动
[JW 09]
。
![](https://csdnimg.cn/release/download_crawler_static/88790138/bg7.jpg)
7
≤
||
相比之下,所有其他已知的证明[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
证明草图:
由于验证者
剩余30页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)