On the Computational Complexity of Monotone Constraint Satisfaction Problems

DOI10.1007/978-3-642-00202-1_25MaRDI QIDQ3605505zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Florian Richoux

Publication date 24 February 2009

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00202-1_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A Dichotomy Theorem for Typed Constraint Satisfaction Problems
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Asking the Metaquestions in Constraint Tractability
• scientific article; zbMATH DE number 1670830
• A proof of the CSP dichotomy conjecture

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Building tractable disjunctive constraints
• Composition sequences for functions over a finite domain.
• scientific article; zbMATH DE number 3162893 (Why is no real title available?)
• scientific article; zbMATH DE number 2149937 (Why is no real title available?)
• On the algebraic structure of combinatorial problems
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Cited in

(12)

• Heuristics and exact algorithms for solving the Monden problem
• Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
• Tractability in constraint satisfaction problems: a survey
• Precise upper and lower bounds for the monotone constraint satisfaction problem
• On the complexity of the model checking problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Adventures in monotone complexity and TFNP
• On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
• A Dichotomy Theorem for Typed Constraint Satisfaction Problems
• Complete problems for monotone NP

This page was built for publication: On the Computational Complexity of Monotone Constraint Satisfaction Problems

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