Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

International audienceThe construction of exact exponential-time algorithms for NP-complete prob- lems 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 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 problem. This result may be in- teresting 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 in more than two clauses) is NP-complete, too. This is in contrast to, for exam- ple, 1-in-3-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 prob- lem 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, NP-complete Boolean languages 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 languages