The complexity of Boolean constraint satisfaction local search problems
type: Item
instance of: scholarly article
title: The complexity of Boolean constraint satisfaction local search problems
zbMATH Open document ID: 1099.68033
author: Philippe Chapdelaine
author: Nadia Creignou
published in: Annals of Mathematics and Artificial Intelligence
publication date: 2005-05-13T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 2168183
zbMATH Keywords: satisfiability
zbMATH Keywords: local search
zbMATH Keywords: complexity
zbMATH Keywords: optimization
zbMATH Keywords: PLS
zbMATH Keywords: PLS-complete
MaRDI profile type: Publication
full work available at URL: s10472-005-0419-3
OpenAlex ID: W2017695771
cites work: Q4230322
cites work: Q4258216
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Q4004338
cites work: A dichotomy theorem for maximum generalized satisfiability problems.
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Gadgets, Approximation, and Linear Programming
cites work: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
cites work: Q3145805
cites work: SAT local search algorithms: Worst-case study
cites work: How easy is local search?
cites work: The approximability of constraint satisfaction problems
cites work: On the greedy algorithm for satisfiability
cites work: On Finding and Verifying Locally Optimal Solutions
cites work: Q4536400
cites work: The complexity of satisfiability problems
cites work: Simple Local Search Problems that are Hard to Solve
DOI: 10.1007/S10472-005-0419-3
description: scientific article; zbMATH DE number 2168183