Distance constraint satisfaction problems

DOI10.1016/j.ic.2015.11.010zbMath1336.68116arXiv1004.3842OpenAlexW1857241714MaRDI QIDQ259047

Barnaby Martin, Victor Dalmau, Antoine Mottet, Manuel Bodirsky, Michael Pinsker

Publication date: 10 March 2016

Published in: Information and Computation, Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

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

zbMATH Keywords

endomorphismsconstraint satisfaction problemsreductscomplexity dichotomyintegers with successorprimitive positive definability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Constraint Satisfaction Problems over the Integers with Successor ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The wonderland of reflections ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Distance constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distance constraint satisfaction problems
• Cyclic terms for \(\text{SD}_{\vee}\) varieties revisited
• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• Complexity of constraints. An overview of current research themes
• Schaefer's Theorem for Graphs
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
• Constraint satisfaction tractability from semi-lattice operations on infinite sets
• The reducts of equality up to primitive positive interdefinability
• Constraint Satisfaction with Countable Homogeneous Templates
• Constraint Satisfaction Problems over the Integers with Successor
• Non-dichotomies in Constraint Satisfaction Complexity
• 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
• Model Theory
• The Lattice of Definability. Origins, Recent Developments, and Further Directions
• Cores of Countably Categorical Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• Recent Results on the Algebraic Approach to the CSP

This page was built for publication: Distance constraint satisfaction problems