Time complexity of constraint satisfaction via universal algebra

DOI10.4230/LIPICS.MFCS.2017.17zbMATH Open1441.68093arXiv1706.05902OpenAlexW2705838778MaRDI QIDQ5111231FDOQ5111231

Biman Roy, Peter Jonsson, Victor Lagerkvist

Publication date: 26 May 2020

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.

Full work available at URL: https://arxiv.org/abs/1706.05902

Recommendations

• Fine-grained time complexity of constraint satisfaction problems
• On the subexponential-time complexity of CSP
• The Time Complexity of Constraint Satisfaction
• The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

zbMATH Keywords

constraint satisfaction problemsuniversal algebraclone theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Which problems have strongly exponential complexity?
• Schaefer's theorem for graphs
• The complexity of temporal constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• On the complexity of \(k\)-SAT
• On the algebraic structure of combinatorial problems
• Complexity of conservative constraint satisfaction problems
• The algebras of partial functions and their invariants
• The Structure of Tractable Constraint Satisfaction Problems
• Closed systems of functions and predicates
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Strong partial clones and the time complexity of SAT problems
• 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
• Complexity Classifications for Logic-Based Argumentation
• Title not available (Why is that?)
• The Complexity of Phylogeny Constraint Satisfaction
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• Title not available (Why is that?)
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Partial Polymorphisms and Constraint Satisfaction Problems
• A Proof of the CSP Dichotomy Conjecture
• As Close as It Gets
• Give Me Another One!
• Time Complexity of Constraint Satisfaction via Universal Algebra

Cited In (6)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing the Complexity of a Valued CSP Language
• The constraint satisfaction problem and universal algebra
• Time Complexity of Constraint Satisfaction via Universal Algebra
• The Time Complexity of Constraint Satisfaction

This page was built for publication: Time complexity of constraint satisfaction via universal algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111231)