Restricted Constraint Satisfaction Problems and the Exponential-time Hypothesis

Abstract: A constraint satisfaction problem (CSP) can be represented as two structures: the structure induced by the variables and the structure induced by the constraint language. Both these parameters are amenable to restrictions which affects the complexity of the resulting problems. In this thesis we shall use both constraint language restrictions and structural restrictions in order to create problems that can be solved as efficiently as possible. The language restrictions are based on creating a language that in terms of frozen partial clone theory has the largest number of polymorphic functions. Such a language can according to the Galois connection between functions and relations be implemented by as many languages as possible and is therefore the Boolean language with the lowest complexity. The structural restrictions are mainly based on limiting the number of times a variable is allowed to occur in an instance. We shall prove that the easiest language does not contain a Delta-matroid relation and is NP-complete even with the very restricted structure where no variable can occur in more than two constraints. We also give a branch-and-reduce algorithm for this problem with time complexity O(1.0493^n). This problem is then related to the exponential-time hypothesis, which postulates that k-SAT is not sub-exponential for k >= 3. We show that the exponential-time hypothesis holds if and only if this restricted problem is not sub-exponential, if and only if all NP-complete Boolean languages are not sub-exponential. In the process we also prove a stronger version of Impagliazzo's sparsification lemma for k-SAT; namely that all finite, NP-complete Boolean languages can be sparsified into each other. This should be contrasted with Santhanam's negative result which states that the same does not hold for all infinite Boolean languages.