A dichotomy theorem for constraint satisfaction problems on a 3-element set

DOI10.1145/1120582.1120584MaRDI QIDQ3546290zbMATH OpenOpenAlexWikidataFDO

Authors Andrei A. Bulatov

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

Mathematics Subject Classification ID

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

Recommendations

• An efficient algorithm for the 3-satisfiability problem
• scientific article; zbMATH DE number 1303558
• Computational complexity of some restricted instances of 3-SAT
• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• A dichotomy theorem for maximum generalized satisfiability problems.
• A new upper bound for 3-SAT
• A numerical approach to 3-SAT

Cited in

(only showing first 100 items - show all)

• Relatively quantified constraint satisfaction
• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• Constraint satisfaction problems: complexity and algorithms
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• On bijunctive predicates over a finite set
• A new tractable class of constraint satisfaction problems
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
• Low-level dichotomy for quantified constraint satisfaction problems
• The complexity of problems for quantified constraints
• The complexity of tropical graph homomorphisms
• Minimal functions on the random graph
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• Lee-Yang theorems and the complexity of computing averages
• Constraint satisfaction problems over semilattice block Mal'tsev algebras
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• The complexity of soft constraint satisfaction
• Combinatorial problems raised from 2-semilattices
• Dichotomy for finite tournaments of mixed-type
• A dichotomy for real weighted Holant problems
• Tractability in constraint satisfaction problems: a survey
• Complexity classifications of Boolean constraint satisfaction problems
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• Precise upper and lower bounds for the monotone constraint satisfaction problem
• Complexity of conservative constraint satisfaction problems
• Why is it hard to obtain a dichotomy for consistent query answering?
• On the CSP Dichotomy Conjecture
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• On the complexity of the model checking problem
• 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
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Galois theory for semiclones
• From graph coloring to constraint satisfaction: there and back again
• On Planar Boolean CSP
• A Galois connection for valued constraint languages of infinite size
• Algebraic properties of valued constraint satisfaction problem
• Necessary conditions for tractability of valued CSPs
• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• List-homomorphism problems on graphs and arc consistency
• The complexity of complex weighted Boolean \#CSP
• Enumerating homomorphisms
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• scientific article; zbMATH DE number 1944123 (Why is no real title available?)
• The complexity of surjective homomorphism problems-a survey
• Colouring, constraint satisfaction, and complexity
• On m-junctive predicates on a finite set
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• The complexity of valued CSPs
• Quantified Constraints in Twenty Seventeen
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• Universal algebraic methods for constraint satisfaction problems
• scientific article; zbMATH DE number 7559384 (Why is no real title available?)
• Beyond Boolean surjective VCSPs
• Testing the Complexity of a Valued CSP Language
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
• The Complexity of Boolean Surjective General-Valued CSPs
• A proof of the CSP dichotomy conjecture
• Hybrid VCSPs with crisp and valued conservative templates
• Constraint satisfaction problems over semilattice block Mal'tsev algebras
• On the computational complexity of non-dictatorial aggregation
• The complexity of counting quantifiers on equality languages
• Constraint satisfaction problems for reducts of homogeneous graphs
• The power of linear programming for general-valued CSPs
• Constraint satisfaction with counting quantifiers
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Quantified constraint satisfaction problem on semicomplete digraphs
• The complexity of general-valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• Binarisation for valued constraint satisfaction problems
• Tractable structures for constraint satisfaction with truth tables
• Quantified constraint satisfaction and the polynomially generated powers property
• Full Constraint Satisfaction Problems
• Mathematical Foundations of Computer Science 2005
• Recent Results on the Algebraic Approach to the CSP
• Dualities for Constraint Satisfaction Problems
• A Logical Approach to Constraint Satisfaction
• Partial Polymorphisms and Constraint Satisfaction Problems
• Introduction to the Maximum Solution Problem
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• The complexity of conservative valued CSPs
• On the minimal constraint satisfaction problem: complexity and generation
• A Dichotomy Theorem for Typed Constraint Satisfaction Problems
• A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• CLAP: A New Algorithm for Promise CSPs
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• An algebraic approach to multi-sorted constraints
• Periodic constraint satisfaction problems: polynomial-time algorithms
• Principles and Practice of Constraint Programming – CP 2004
• Tractable constraints on ordered domains
• Bipartite 3-regular counting problems with mixed signs

This page was built for publication: A dichotomy theorem for constraint satisfaction problems on a 3-element set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546290)