On Problems as Hard as CNFSAT-猫眼课题宝

DOI：

10.1145/2925416

发表时间：

2011-12

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Marek Cygan;Holger Dell;D. Lokshtanov;D. Marx;Jesper Nederlof;Y. Okamoto;R. Paturi;Saket Saurabh

在过去的十年里，精确指数时间算法在ﬁ领域蓬勃发展。虽然穷举搜索仍然是一些基本问题的最快已知算法，但对于无数问题，包括图着色、哈密尔顿路、支配集和3-ﬃ-sat，已经找到了di CNF崇拜和非平凡指数时间算法。在某些情况下，进一步改进这些算法似乎遥不可及。CNF-sat问题是平凡穷举搜索算法在O(2n)时间内运行的典型例子，其中n是输入公式中变量的个数。虽然已有的CNF-sat的非平凡算法运行时间为o(2，n)，但没有一种算法能够将增长率2提高到一个较小的常数，因此很自然地猜测2是最优增长率。Imagliazzo和Paturi[JCSS2001]的强指数时间假说(Seth)更进一步，它断言，对于每个(CID：15)和1，存在一个(大)整数k，使得k-CNF-Sat不能在时间2(CID：15)n内计算。本文证明了，对于任意(Cid：15)&lt；1，除非Seth失败，否则不能在O(2(Cid：15)n)时间内计算命中集合、集合分裂和NAE-sat问题。这里n是输入中的元素或变量的数量。对于这些问题，我们实际上在某种意义上得到了与赛斯的等价性。我们猜想Seth对集合覆盖也有类似的表述，并证明了在这种假设下，Steiner树、连通顶点覆盖、集合划分以及子集和的伪多项式时间算法都不能得到显著的改进。最后，我们证明了我们关于集合覆盖的硬度的假设是正确的

The ﬁeld of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, diﬃcult and non-trivial exponential time algorithms have been found for a myriad of problems, including Graph Coloring , Hamiltonian Path , Dominating Set and 3- CNF-Sat . In some instances, improving these algorithms further seems to be out of reach. The CNF-Sat problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O (2 n ), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-Sat that run in time o (2 n ), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every (cid:15) < 1, there is a (large) integer k such that k - CNF-Sat cannot be computed in time 2 (cid:15)n . In this paper, we show that, for every (cid:15) < 1, the problems Hitting Set , Set Splitting , and NAE-Sat cannot be computed in time O (2 (cid:15)n ) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for Set Cover , and prove that, under this assumption, the fastest known algorithms for Steiner Tree , Connected Vertex Cover , Set Partitioning , and the pseudo-polynomial time algorithm for Subset Sum cannot be signiﬁcantly improved. Finally, we justify our assumption about the hardness of Set Cover by showing

On Problems as Hard as CNFSAT

文献摘要

被引文献

相似文献