The complexity of Boolean constraint satisfaction local search problems
From MaRDI portal
Publication:1777392
DOI10.1007/s10472-005-0419-3zbMath1099.68033OpenAlexW2017695771MaRDI QIDQ1777392
Nadia Creignou, Philippe Chapdelaine
Publication date: 13 May 2005
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-005-0419-3
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
Cites Work
- A dichotomy theorem for maximum generalized satisfiability problems.
- How easy is local search?
- On the greedy algorithm for satisfiability
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- Complexity of generalized satisfiability counting problems
- SAT local search algorithms: Worst-case study
- The Approximability of Constraint Satisfaction Problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Simple Local Search Problems that are Hard to Solve
- On Finding and Verifying Locally Optimal Solutions
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Gadgets, Approximation, and Linear Programming
- The complexity of satisfiability problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
