Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity
Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity
复制标题
改进的 Merlin–Arthur 协议解决细粒度复杂性的核心问题
DOI：
10.1007/s00453-023-01102-6
复制
发表时间：
2023
期刊：
影响因子：
1.1
通讯作者：
Williams, Ryan
中科院分区：
文献类型：
--
作者：
Akmal, Shyan;Chen, Lijie;Jin, Ce;Raj, Malvika;Williams, Ryan
在梅林-亚瑟证明系统中，证明验证者（亚瑟）以概率1接受（来自梅林的）有效证明，并以任意接近1的概率拒绝无效证明。这样一个系统的运行时间被定义为梅林证明的长度加上亚瑟的运行时间。我们为细粒度复杂性中的一些关键问题提供了新的Merlin-Arthur证明系统。在某些情况下，我们的证明系统具有最佳运行时间。我们的主要结果包括：证明一个n整数列表没有3-SUM解可以在Merlin-Arthur时间内完成。之前，Carmosino等人[ITCS 2016]证明了该问题有一个在时间上运行的非确定性算法（即存在一个长度证明和一个在时间上运行的确定性验证器的证明系统），可以在Merlin-Arthur时间内计算ann-节点图中总边权重等于零的k-团的数量（其中）。对于oddk，这个界限可以进一步改进稀疏图：例如，计算anm-edge图中零权三角形的数量可以在Merlin-Arthur时间内完成。威廉姆斯[CCC '16]和Björklund和Kaski [PODC' 16]提出的Merlin-Arthur协议只能计算无权图中的k-团，且对smallk的计算时间较差，而计算ann-节点图的全对最短距离矩阵可以在Merlin-Arthur时间内完成.注意，这是最佳的，因为矩阵通常可以没有零个元素。此前，Carmosino等人[ITCS 2016]表明该问题具有非确定性时间算法。可以在Merlin-Arthur时间内证明ann-variablek-CNF不可满足。我们还观察到R.威廉姆斯[CCC '16]的前一个Merlin-Arthur协议的代数化障碍：特别是，他的协议代数化，我们观察到没有代数化协议fork-UNSAT在时间上运行。因此，我们必须利用非代数化性质来获得我们的新协议。证明量化布尔公式为真可以在Merlin-Arthur时间内完成。以前，唯一的非平凡的结果已知沿着这些线路是一个亚瑟-梅林-亚瑟协议（其中梅林的证明依赖于一些亚瑟的硬币）运行intime.Due这些问题在细粒度的复杂性的中心，我们的结果有许多其他感兴趣的问题的后果。例如，我们的工作意味着证明整数没有子集和解决方案可以在Merlin-Arthur时间内完成，改进了Nederlof [IPL 2017]之前的最佳协议。
In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running intime (that is, there is a proof system with proofs of lengthand a deterministic verifier running intime).Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time(where). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time. Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk.Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time. Note this is optimal, as the matrix can havenonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has annondeterministic time algorithm.Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time. We also observe an algebrization barrier for the previous-time Merlin–Arthur protocol of R. Williams [CCC’16] forSAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running intime. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time. Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running intime.Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time, improving on the previous best protocol by Nederlof [IPL 2017] which tooktime.
登录
查看更多内容
DOI：
10.4230/lipics.itcs.2018.18
发表时间：
2017
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Oded Goldreich;G. Rothblum
通讯作者：
Oded Goldreich;G. Rothblum
影响因子：
1.4
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
UP 的高效批量验证
DOI：
--
发表时间：
2018
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Omer Reingold;G. Rothblum;Ron D. Rothblum
通讯作者：
Ron D. Rothblum
DOI：
10.1016/j.ipl.2016.09.002
发表时间：
2016-02
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
Jesper Nederlof
通讯作者：
Jesper Nederlof
单色三角形、三角形列表和 APSP
DOI：
--
发表时间：
2020
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
V. V. Williams;Yinzhan Xu
通讯作者：
Yinzhan Xu