• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >AM with Multiple Merlins
【24h】

AM with Multiple Merlins

机译：我有多个merlins

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n^{1/2+o(1)} bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n^{(log n)^{1-o(1)}} time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k) = AM for all k=poly(n). The key to this result is a sub sampling theorem for free games, which follows from powerful results by Alon et al. And Barak et al. On sub sampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random sub game.
机译：我们介绍并研究了一个新的互动证明模式：AM（k），或亚瑟 - Merlin，与K非沟通Merlins。与更好的MIP不同，这里的假设是每个Merlin从亚瑟接收一个独立的随机挑战。该模型的一个动机（我们详细探讨）来自它与量子复杂性等级QMA（k）之间的紧密模拟，但AM（k）模型在自己的右边也是自然的。我们通过为3SAT提供AM（2）协议来说明多个Merlins的力量，其中Merlins的挑战和响应仅由每个N ^ {1/2 + O（1）}组成。我们的协议结果结果是，假设指数时间假设（Eth），任何用于近似密集CSP的算法，具有多项式字母表必须采用n ^ {（log n）^ {1-O（1）}}时间。近乎匹配这个下限的算法是已知的，但他们从未解释过他们的运行时间。 Brandao和Harrow也最近利用了我们的3SAT协议来显示Quaasi oneMomial的硬度，以估计某些纠缠游戏的价值。在另一个方向上，我们给出了一个简单的QuaSieioMoMomial-Time近似算法，用于免费游戏，并使用它证明假设eth，我们的3SAT协议基本上是最佳的。更一般地，我们表明多个Merlins从未提供超过一个多项式优势：即，AM（k）= Am对于所有k = poly（n）。此结果的关键是免费游戏的子采样定​​理，从而从Alon等人的强大结果遵循。和巴拉克等人。在子采样密集CSP上，并表示任何自由游戏的值可以通过对数大小的随机子游戏的值密切近似。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号