Time complexity of constraint satisfaction via universal algebra
From MaRDI portal
Publication:5111231
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)
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.
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
Cites work
- scientific article; zbMATH DE number 1948177 (Why is no real title available?)
- scientific article; zbMATH DE number 783783 (Why is no real title available?)
- scientific article; zbMATH DE number 6028114 (Why is no real title available?)
- 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
- A proof of the CSP dichotomy conjecture
- As Close as It Gets
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Closure properties of constraints
- Complexity Classifications for Logic-Based Argumentation
- Complexity of conservative constraint satisfaction problems
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
- Give me another one!
- Handbook of constraint programming.
- On the algebraic structure of combinatorial problems
- On the complexity of \(k\)-SAT
- Partial Polymorphisms and Constraint Satisfaction Problems
- Strong partial clones and the time complexity of SAT problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Structure of Tractable Constraint Satisfaction Problems
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
- The algebras of partial functions and their invariants
- The complexity of phylogeny constraint satisfaction
- The complexity of satisfiability problems
- The complexity of temporal constraint satisfaction problems
- Time complexity of constraint satisfaction via universal algebra
- Which problems have strongly exponential complexity?
Cited in
(17)- The Time Complexity of Constraint Satisfaction
- On exact algorithms for the permutation CSP
- Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- scientific article; zbMATH DE number 7536562 (Why is no real title available?)
- scientific article; zbMATH DE number 1222101 (Why is no real title available?)
- Time complexity of constraint satisfaction via universal algebra
- Why are CSPs based on partition schemes computationally hard?
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Testing the Complexity of a Valued CSP Language
- On the subexponential-time complexity of CSP
- Precise upper and lower bounds for the monotone constraint satisfaction problem
- The constraint satisfaction problem and universal algebra
- A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
- Satisfiability certificates verifiable in subexponential time
- An initial study of time complexity in infinite-domain constraint satisfaction
- Fine-grained time complexity of constraint satisfaction problems
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)
