期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 of n integers has no 3-SUM solution can be done in Merlin-Arthur time O(n). Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in O(n15) time (that is, there is a proof system with proofs of length O(n15) and a deterministic verifier running in O(n15) time). Counting the number of k-cliques with total edge weight equal to zero in an n-node graph can be done in Merlin-Arthur time O(nk2) (where k3 ). For odd k, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in an m-edge graph can be done in Merlin-Arthur time O(m). Previous Merlin-Arthur protocols by Williams [CCC'16] and Bj\"orklund and Kaski [PODC'16] could only count k-cliques in unweighted graphs, and had worse running times for small k. Computing the All-Pairs Shortest Distances matrix for an n-node graph can be done in Merlin-Arthur time O(n2). Note this is optimal, as the matrix can have (n2) nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an O(n294) nondeterministic time algorithm. Certifying that an n-variable k-CNF is unsatisfiable can be done in Merlin-Arthur time 2n2−nO(k) . We also observe an algebrization barrier for the previous 2n2poly(n) -time Merlin-Arthur protocol of R. Williams [CCC'16] for #SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol for k-UNSAT running in 2n2n(1) time. 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 24n5poly(n) . 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 in 22n3poly(n) time. 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 to n integers can be done in Merlin-Arthur time 2n3poly(n) , improving on the previous best protocol by Nederlof [IPL 2017] which took 2049991npoly(n) time.
