Precise upper and lower bounds for the monotone constraint satisfaction problem

DOI10.1007/978-3-662-48057-1_28zbMATH Open1465.68106OpenAlexW2407741447MaRDI QIDQ2946352FDOQ2946352

Authors: Victor Lagerkvist 

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48057-1_28

Recommendations

• Fine-grained time complexity of constraint satisfaction problems
• Time complexity of constraint satisfaction via universal algebra
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• The Time Complexity of Constraint Satisfaction
• On the subexponential-time complexity of CSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Completeness of Park induction
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of satisfiability problems
• On the complexity of \(k\)-SAT
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• The complexity of satisfiability of small depth circuits
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Basics of Galois Connections
• Disjunctive closures for knowledge compilation
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

Cited In (4)

• The Monotone Satisfiability Problem with Bounded Variable Appearances
• General lower bounds and improved algorithms for infinite-domain CSPs
• Fine-grained time complexity of constraint satisfaction problems
• The Time Complexity of Constraint Satisfaction

This page was built for publication: Precise upper and lower bounds for the monotone constraint satisfaction problem

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