The complexity of Boolean constraint satisfaction local search problems

DOI10.1007/S10472-005-0419-3MaRDI QIDQ1777392zbMATH OpenOpenAlexFDO

Authors Philippe Chapdelaine, Nadia Creignou

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

zbMATH Keywords

optimizationcomplexitylocal searchsatisfiabilityPLSPLS-complete

Mathematics Subject Classification ID

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)

Recommendations

• A note on the complexity of local search problems
• scientific article; zbMATH DE number 18531
• New local search approximation techniques for maximum generalized satisfiability problems
• How easy is local search?
• On the \(\mathcal {PLS}\)-complexity of maximum constraint assignment

Cites work

• scientific article; zbMATH DE number 6118223 (Why is no real title available?)
• scientific article; zbMATH DE number 54154 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1759450 (Why is no real title available?)
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A dichotomy theorem for maximum generalized satisfiability problems.
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Gadgets, Approximation, and Linear Programming
• How easy is local search?
• On Finding and Verifying Locally Optimal Solutions
• On the greedy algorithm for satisfiability
• SAT local search algorithms: Worst-case study
• Simple Local Search Problems that are Hard to Solve
• The approximability of constraint satisfaction problems
• The complexity of satisfiability problems

Cited in

(9)

• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Graph-Theoretic Concepts in Computer Science
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Approximation of Boolean functions by local search
• On the Hardness of Losing Weight
• On the hardness of losing weight
• Representing fitness landscapes by valued constraints to understand the complexity of local search
• On the \(\mathcal {PLS}\)-complexity of maximum constraint assignment
• scientific article; zbMATH DE number 2084740 (Why is no real title available?)

This page was built for publication: The complexity of Boolean constraint satisfaction local search problems

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