Non-dichotomies in Constraint Satisfaction Complexity

DOI10.1007/978-3-540-70583-3_16zbMath1155.68403OpenAlexW1601269853MaRDI QIDQ3519501

Manuel Bodirsky, Martin Grohe

Publication date: 19 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70583-3_16

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Constraint satisfaction and semilinear expansions of addition over the rationals and the reals ⋮ Tractability in constraint satisfaction problems: a survey ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains ⋮ \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ Tractability conditions for numeric CSPs ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Unnamed Item ⋮ Causal graphs and structurally restricted planning ⋮ Unnamed Item ⋮ Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures ⋮ Tractable combinations of theories via sampling ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Piecewise linear valued constraint satisfaction problems with fixed number of variables ⋮ Complexity of existential positive first-order logic ⋮ Description logics with concrete domains and general concept inclusions revisited ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties ⋮ Distance constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of infinite \(H\)-colouring
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Reasoning about temporal relations
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• Constraint Satisfaction Problems with Infinite Templates
• Countable homogeneous relational structures and ℵ₀-categorical theories