Title: Time Complexity of Constraint Satisfaction via Universal Algebra,
Abstract: The exponential-time hypothesis (ETH) states that 3-SAT is not solvable in
subexponential time, i.e. not solvable in O(c^n) time for arbitrary c > 1,
where n denotes the number of variables. Problems like k-SAT can be viewed as
special cases of the constraint satisfaction problem (CSP), which is the
problem of determining whether a set of constraints is satisfiable. In this
paper we study thef worst-case time complexity of NP-complete CSPs. Our main
interest is in the CSP problem parameterized by a constraint language Gamma
(CSP(Gamma)), and how the choice of Gamma affects the time complexity. It is
believed that CSP(Gamma) is either tractable or NP-complete, and the algebraic
CSP dichotomy conjecture gives a sharp delineation of these two classes based
on algebraic properties of constraint languages. Under this conjecture and the
ETH, we first rule out the existence of subexponential algorithms for
finite-domain NP-complete CSP(Gamma) problems. This result also extends to
certain infinite-domain CSPs and structurally restricted CSP(Gamma) problems.
We then begin a study of the complexity of NP-complete CSPs where one is
allowed to arbitrarily restrict the values of individual variables, which is a
very well-studied subclass of CSPs. For such CSPs with finite domain D, we
identify a relation SD such that (1) CSP({SD}) is NP-complete and (2) if
CSP(Gamma) over D is NP-complete and solvable in O(c^n) time, then CSP({SD}) is
solvable in O(c^n) time, too. Hence, the time complexity of CSP({SD}) is a
lower bound for all CSPs of this particular kind. We also prove that the
complexity of CSP({SD}) is decreasing when |D| increases, unless the ETH is
false. This implies, for instance, that for every c>1 there exists a
finite-domain Gamma such that CSP(Gamma) is NP-complete and solvable in O(c^n)
time.