On the CSP Dichotomy Conjecture

DOI10.1007/978-3-642-20712-9_26MaRDI QIDQ3007637zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov

Publication date 17 June 2011

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20712-9_26

zbMATH Keywords

constraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Simple Algorithm for Mal'tsev Constraints
• Affine Systems of Equations and Counting Infinitary Logic
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Constraint Satisfaction Problems of Bounded Width
• Constraint Satisfaction, Logic and Forbidden Patterns
• Constraints, consistency and closure
• Constraints, MMSNP and expander relational structures
• Dualities for Constraint Satisfaction Problems
• Generalized Majority-Minority Operations are Tractable
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• Monotone monadic SNP and constraint satisfaction
• NP by Means of Lifts and Shadows
• OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
• On the complexity of H-coloring
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• On the Structure of Polynomial Time Reducibility
• Recent Results on the Algebraic Approach to the CSP
• Synthesizing constraint expressions
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The structure of finite algebras
• Tractability and learnability arising from algebras with few subpowers
• Undirected ST-connectivity in log-space
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems

Cited in

(10)

• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• scientific article; zbMATH DE number 5999552 (Why is no real title available?)
• On Planar Boolean CSP
• 2 -Way vs.d -Way Branching for CSP
• scientific article; zbMATH DE number 5531977 (Why is no real title available?)
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Parameterized complexity of the workflow satisfiability problem
• CSP gaps and reductions in the lasserre hierarchy
• On the complexity of CSP-based ideal membership problems
• Graphs of finite algebras: edges, and connectivity

This page was built for publication: On the CSP Dichotomy Conjecture

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