Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem

DOI10.1007/978-3-662-48057-1_28zbMath1465.68106OpenAlexW2407741447MaRDI QIDQ2946352

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)

Related Items (1)

General lower bounds and improved algorithms for infinite-domain CSPs

Cites Work

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

This page was built for publication: Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem