文章基本信息

标题：On Super Strong ETH
本地全文：下载
作者：Nikhil Vyas ; Ryan Williams
期刊名称：Journal of Artificial Intelligence Research
印刷版ISSN：1076-9757
出版年度：2021
卷号：70
页码：473-495
出版社：American Association of Artificial
摘要：Multiple known algorithmic paradigms (backtracking; local search and the polynomial method) only yield a 2n(1-1/O(k)) time algorithm for k-SAT in the worst case. For this reason; it has been hypothesized that the worst-case k-SAT problem cannot be solved in 2n(1-f(k)/k) time for any unbounded function f. This hypothesis has been called the "Super-Strong ETH"; modelled after the ETH and the Strong ETH. It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the "critical threshold"; where the clause-to-variable ratio is such that randomly chosen instances are satisfiable with probability 1/2. We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k-SAT and planted k-SAT for any clause-to-variable ratio. For example; given any random k-SAT instance F with n variables and m clauses; our algorithm decides satisfiability for F in 2n(1-c*log(k)/k) time with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi; Pudlak; and Zane (1999). The Unique k-SAT problem is the special case where there is at most one satisfying assignment. Improving prior reductions; we show that the Super-Strong ETHs for Unique k-SAT and k-SAT are equivalent. More precisely; we show the time complexities of Unique k-SAT and k-SAT are very tightly correlated: if Unique k-SAT is in 2n(1-f(k)/k) time for an unbounded f; then k-SAT is in 2n(1-f(k)/(2k)) time.
关键词：satisfiability;constraint satisfaction;mathematical foundations