Time Complexity of Constraint Satisfaction via Universal Algebra

DOI10.4230/LIPIcs.MFCS.2017.17zbMath1441.68093arXiv1706.05902OpenAlexW2705838778MaRDI QIDQ5111231

Biman Roy, Peter Jonsson, Victor Lagerkvist

Publication date: 26 May 2020

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

zbMATH Keywords

constraint satisfaction problemsuniversal algebraclone theory

Mathematics Subject Classification ID

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

Related Items (3)

Unnamed Item ⋮ Testing the Complexity of a Valued CSP Language ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra

Cites Work

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

This page was built for publication: Time Complexity of Constraint Satisfaction via Universal Algebra