The complexity of equality constraint languages

DOI10.1007/s00224-007-9083-9zbMath1148.68025OpenAlexW2087215337MaRDI QIDQ929295

Manuel Bodirsky, Jan Kára

Publication date: 17 June 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9083-9

zbMATH Keywords

Computational complexityConstraint satisfactionClones on infinite domainsLogic in computer science

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Tractability in constraint satisfaction problems: a survey ⋮ Constraint Satisfaction Problems over the Integers with Successor ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Reconstructing the topology of clones ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ The complexity of counting quantifiers on equality languages ⋮ Minimal functions on the random graph ⋮ Unnamed Item ⋮ Schaefer's Theorem for Graphs ⋮ Unnamed Item ⋮ Maximal infinite-valued constraint languages ⋮ Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ The Complexity of Quantified Constraints Using the Algebraic Formulation ⋮ Unnamed Item ⋮ The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of satisfiability problems: Refining Schaefer's theorem
• NP is as easy as detecting unique solutions
• Local and global relational consistency
• The maximal clones on countable sets that include all permutations.
• Closed systems of functions and predicates
• Maximal clones on uncountable sets that include all permutations
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Building tractable disjunctive constraints
• Constraint Satisfaction with Countable Homogeneous Templates
• The Complexity of Equality Constraint Languages
• `` Strong NP-Completeness Results
• Reasoning about temporal relations
• Classifying the Complexity of Constraints Using Finite Algebras
• Datalog and Constraint Satisfaction with Infinite Templates
• Constraint Satisfaction Problems with Infinite Templates

This page was built for publication: The complexity of equality constraint languages