2017/06/19 by Peter Jonsson, Peter Jönsson, Victor Lagerkvist +5 · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algebra over a field #Complexity of constraint satisfaction #Computational Complexity (cs.CC) #Computer science #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction #Constraint satisfaction problem #FOS: Computer and information sciences #Formal Methods in Verification #Local consistency #Mathematics #Pure mathematics #Statistics #Theoretical computer science #Universal algebra #cs.CC
paper · pdf · doi:10.48550/arxiv.1706.05902
published in arXiv (Cornell University) (Cornell University)
arxiv created 2017/06/19 · openalex publication_date 2017/06/19 · arxiv updated 2017/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The exponential-time hypothesis (ETH) states that 3-SAT is not solvable in subexponential time, i.e. not solvable in O(cn) 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(cn) time, then CSP(SD) is solvable in O(cn) 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(cn) time.