A dichotomy theorem for constraint satisfaction problems on a 3-element set
From MaRDI portal
Publication:3546290
DOI10.1145/1120582.1120584zbMath1316.68057OpenAlexW1997649256MaRDI QIDQ3546290
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1120582.1120584
Analysis of algorithms and problem complexity (68Q25) 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 (96)
Quantified Constraint Satisfaction Problem on Semicomplete Digraphs ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Non-local configuration of component interfaces by constraint satisfaction ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ On Planar Boolean CSP ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ The complexity of constraint satisfaction games and QCSP ⋮ On the Complexity of the Model Checking Problem ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ A Dichotomy Theorem for Polynomial Evaluation ⋮ Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ Galois theory for semiclones ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ On the Boolean connectivity problem for Horn relations ⋮ Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem ⋮ Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering? ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ List-homomorphism problems on graphs and arc consistency ⋮ The complexity of complex weighted Boolean \#CSP ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ Unnamed Item ⋮ Conservative constraint satisfaction re-revisited ⋮ A new line of attack on the dichotomy conjecture ⋮ Computational complexity of covering three-vertex multigraphs ⋮ Enumerating homomorphisms ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Quantified Constraint Satisfaction and the Polynomially Generated Powers Property ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ The complexity of problems for quantified constraints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ Quantified Constraints in Twenty Seventeen ⋮ Computational complexity of auditing finite attributes in statistical databases ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ On bijunctive predicates over a finite set ⋮ On the CSP Dichotomy Conjecture ⋮ On the Computational Complexity of Non-Dictatorial Aggregation ⋮ Complexity of the satisfiability problem for multilinear forms over a finite field ⋮ The complexity of counting quantifiers on equality languages ⋮ Lee-Yang theorems and the complexity of computing averages ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ The Helly property and satisfiability of Boolean formulas defined on set families ⋮ Tractable structures for constraint satisfaction with truth tables ⋮ Quantified constraint satisfaction and the polynomially generated powers property ⋮ The complexity of tropical graph homomorphisms ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Minimal functions on the random graph ⋮ Combinatorial problems raised from 2-semilattices ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ CSP duality and trees of bounded pathwidth ⋮ Unnamed Item ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Unnamed Item ⋮ Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination ⋮ On the Computational Complexity of Monotone Constraint Satisfaction Problems ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ On m-Junctive Predicates on a Finite Set ⋮ Relatively quantified constraint satisfaction ⋮ Testing the Complexity of a Valued CSP Language ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ Unnamed Item ⋮ On weak positive predicates over a finite set ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems ⋮ Partial Polymorphisms and Constraint Satisfaction Problems ⋮ Introduction to the Maximum Solution Problem ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns ⋮ Unnamed Item ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮ A dichotomy for real weighted Holant problems
This page was built for publication: A dichotomy theorem for constraint satisfaction problems on a 3-element set
