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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(4)

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

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)