《On Problems as Hard as CNF-SAT - Stanford University》由会员分享，可在线阅读，更多相关《On Problems as Hard as CNF-SAT - Stanford University（25页珍藏版）》请在金锄头文库上搜索。
1、On Problems as Hard as CNF-SATMarek CyganHolger DellDaniel LokshtanovD aniel MarxJesper NederlofkYoshio OkamotoRamamohan PaturiSaket SaurabhMagnus Wahlstr omJune 7, 2012AbstractThe field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive sear
2、ch remains asymptotically the fastest known algorithm forsome basic problems, difficult 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 furthe
3、r 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(2n), 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(2n), no algorit
4、hm 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 ? 0 such that there exists
5、a randomized 2?npoly(m)-time algorithm for whose error probability is at most 1/3.The optimal growth rate of with respect to n is C := 2(/n). If the infimum in thedefinition above is a minimum, then has an algorithm that runs in time Cnpoly(m) and no algorithm for can have a running time cnpoly(m) f
6、or any c C. We formally define SETH as the assertion that limk(k-CNF-Sat/n) = 1. We remark that it is consistent with current knowledge that SETH fails and yet CNF-Sat does not have 2?npoly(m)-algorithms for any ? 0, we have ?(k,c)-Sparse-CNF-Sat/n? ?k-CNF-Sat/n? ?(k,c)-Sparse-CNF-Sat/n?+?,where the
7、 first inequality is trivial and the second inequality follows from the sparsificationlemma. The density c = c(k,?) is the sparsification constant, and the best known bound is c(k,?) = (k/?)3kCIP06. By setting ? = ?(k) = (1), this immediately yields the following theorem.Theorem 3.1 (IPZ01; CIP06).
8、For every function c = c(k) (k)3k, we havelim k? k-CNF-Sat/n? = lim k? (k,c)-Sparse-CNF-Sat/n? .Hence, SETH is equivalent to the right-hand side being equal to 1. In DHM+12 it wasobserved that the sparsification lemma can be made parsimonious, which gives the following equality for the same function
9、s c = c(k):lim k? k-CNF-Sat/n? = lim k? (k,c)-Sparse-CNF-Sat/n? .We define -SETH as the assertion that these limits are equal to 1. The isolation lemmas for k-CNF formulas CIK+03; Tra08 immediately yield that SETH implies -SETH. More precisely, we have the following theorem.Theorem 3.2 (CIK+03; Tra0
10、8). limk(k-CNF-Sat/n) limk(k-CNF-Sat/n).3.2From CNF-SAT to Hitting SetThe following construction will be useful in this subsection and in Subsection 3.4. Given a CNF formula = C1 . Cmover n variables v1,.,vnand an odd integer p 3 that divides n, we construct the set system F,p 2Uas follows.1. Let p0
11、be the odd integer p0= p + 2dlog2pe, and let U = u1,.,un0 with n0= p0 n/p.2. Partition the variables of into blocks Viof size p, i.e., Vi:= vpi+1,.,vp(i+1).3. Partition U into blocks Uiof size p0, i.e., Ui= up0i+1,.,up0(i+1).4. Choose an arbitrary injective function i: 2Vi?Ui dp0/2e? . This exists s
12、ince?Ui dp0/2e?=?p0 dp0/2e? 2p0p02pp2 p + 2dlog2pe 2p=?2Vi?.6We think of ias a mapping that, given an assignment to the variables of Vi, associates with it a subset of Uiof size dp0/2e.5. If X ?Ui dp0/2e?for some i, then add the set X to F,p.6. If X ?Ui bp0/2c?for some i such that 1i(Ui X) = , then
13、add the set X to F,p.7. For every clause C of , do the following: Let I = 1 j n p| C contains a variable of block Vj; For every i I, we let Aibe the set ? A ?Ui bp0/2c?some assignment in 1 i(Ui A) sets all variables in C Vito false? ; For every tuple (Ai)iIwith Ai Ai, add the setS iIAito F,p.Lemma 3
14、.3. For every n-variable CNF formula and every odd integer p 3 that divides n, the number of satisfying assignments of is equal to the number of hitting sets of size dp0 2en pof the set system F,p, where p0= p + 2dlog2pe.Proof. For convenience denote g =n p. Define : 2V 2Uas (A) =Sg i=1i(A Vi). Note
15、 that is injective, since for every i, iis injective. Hence to prove the lemma, it is sufficient to prove that (1) A is a satisfying assignment if and only if (A) is a hitting set of size dp0 2eg, and (2) if there is no assignment A V such that (A) = H, than no set H U of size dp0 2egis a hitting se
16、t of F,p. For the forward direction of (1), note that the sets added in Step 5 are hit by the pigeon-hole principle since |i(A Vi)| = dp0 2e and p0is odd. For the sets added in Step 6, consider the following. The set X of size bp0/2c is added because for some i, 1i(Ui X) = . Thus i(A Vi) automatically hi
