Paper Info
Title
Complexity of SAT problems, clone theory and the exponential time hypothesis
Abstract
The construction of exact exponential-time algorithms for NP-complete problems has for some time been a very active research area. Unfortunately, there is a lack of general methods for studying and comparing the time complexity of algorithms for such problems. We propose such a method based on clone theory and demonstrate it on the SAT problem. Schaefer has completely classified the complexity of SAT with respect to the set of allowed relations and proved that this parameterized problem exhibits a dichotomy: it is either in P or is NP-complete. We show that there is a certain partial order on the NP-complete SAT problems with a close connection to their worst-case time complexities; if a problem SAT(S) is below a problem SAT(S') in this partial order, then SAT(S') cannot be solved strictly faster than SAT(S). By using this order, we identify a relation R such that SAT({R}) is the computationally easiest NP-complete SAT(S') problem. This result may be interesting when investigating the borderline between P and NP since one appealing way of studying this borderline is to identify problems that, in some sense, are situated close to it (such as a 'very hard' problem in P or a 'very easy' NP-complete problem). We strengthen the result by showing that SAT({R})-2 (i.e. SAT({R}) restricted to instances where no variable appears more than twice) is NP-complete, too. This is in contrast to, for example, 1-in-3-SAT (or even CNF-SAT), which is in P under the same restriction. We then relate SAT({R})-2 to the exponential-time hypothesis (ETH) and show that ETH holds if and only if SAT({R})-2 is not sub-exponential. This constitutes a strong connection between ETH and the SAT problem under both severe relational and severe structural restrictions, and it may thus serve as a tool for studying the borderline between sub-exponential and exponential problems. In the process, we also prove a stronger version of Impagliazzo et al.'s sparsification lemma for k-SAT; namely that all finite Boolean constraint languages S and S' such that SAT(·) is NP-complete can be sparsified into each other. This should be compared with Santhanam and Srinivasan's recent negative result which states that the same does not hold for all infinite Boolean constraint languages.
Year
DOI
Venue
2013
10.5555/2627817.2627909
SODA
Keywords
Field
DocType
algorithms,design,complexity measures and classes,general,theory,numerical algorithms and problems,computer science
#SAT,Discrete mathematics,Parameterized complexity,Combinatorics,Exponential function,Sat problem,If and only if,Time complexity,Lemma (mathematics),Mathematics,Exponential time hypothesis
Conference
ISBN
Citations 
PageRank 
978-1-61197-251-1
14
0.81
References 
Authors
21
4
Name
Order
Citations
PageRank
Peter Jonsson170054.04
Victor Lagerkvist23910.73
Gustav Nordh312110.40
Bruno Zanuttini428925.43