The complexity of Boolean constraint satisfaction local search problems (Q1777392): Difference between revisions

@@ Property / DOI @@
-.1007/s10472-005-0419-3
@@ Property / DOI: 10.1007/s10472-005-0419-3 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s10472-005-0419-3
+Normal rank
@@ Property / OpenAlex ID @@
+W2017695771
@@ Property / OpenAlex ID: W2017695771 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4230322
@@ Property / cites work: Q4230322 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258216
@@ Property / cites work: Q4258216 / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Q4004338
@@ Property / cites work: Q4004338 / rank @@
+Normal rank
@@ Property / cites work @@
+A dichotomy theorem for maximum generalized satisfiability problems.
+Normal rank
@@ Property / cites work @@
+Complexity of generalized satisfiability counting problems
+Normal rank
@@ Property / cites work @@
+Complexity Classifications of Boolean Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+Gadgets, Approximation, and Linear Programming
@@ Property / cites work: Gadgets, Approximation, and Linear Programming / rank @@
+Normal rank
@@ Property / cites work @@
+A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
+Normal rank
@@ Property / cites work @@
+Q3145805
@@ Property / cites work: Q3145805 / rank @@
+Normal rank
@@ Property / cites work @@
+SAT local search algorithms: Worst-case study
@@ Property / cites work: SAT local search algorithms: Worst-case study / rank @@
+Normal rank
@@ Property / cites work @@
+How easy is local search?
@@ Property / cites work: How easy is local search? / rank @@
+Normal rank
@@ Property / cites work @@
+The Approximability of Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+On the greedy algorithm for satisfiability
@@ Property / cites work: On the greedy algorithm for satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+On Finding and Verifying Locally Optimal Solutions
+Normal rank
@@ Property / cites work @@
+Q4536400
@@ Property / cites work: Q4536400 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of satisfiability problems
@@ Property / cites work: The complexity of satisfiability problems / rank @@
+Normal rank
@@ Property / cites work @@
+Simple Local Search Problems that are Hard to Solve
+Normal rank
@@ Property / DOI @@
+.1007/S10472-005-0419-3
@@ Property / DOI: 10.1007/S10472-005-0419-3 / rank @@
+Normal rank