The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs (Q2475410): Difference between revisions

@@ 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.1016/j.jcss.2007.06.015
+Normal rank
@@ Property / OpenAlex ID @@
+W2092928619
@@ Property / OpenAlex ID: W2092928619 / rank @@
+Normal rank
@@ Property / cites work @@
+Two systems for proving tautologies, based on the split method
+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 @@
+Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
+Normal rank
@@ Property / cites work @@
+Parametrized complexity theory.
@@ Property / cites work: Parametrized complexity theory. / rank @@
+Normal rank
@@ Property / cites work @@
+SAT-Problems and Reductions with Respect to the Number of  Variables
+Normal rank
@@ Property / cites work @@
+A necessary condition on minimal cube numberings
@@ Property / cites work: A necessary condition on minimal cube numberings / rank @@
+Normal rank
@@ Property / cites work @@
+Q4736839
@@ Property / cites work: Q4736839 / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Q5501274
@@ Property / cites work: Q5501274 / rank @@
+Normal rank
@@ Property / cites work @@
+Solving satisfiability in less than \(2^ n\) steps
+Normal rank
@@ Property / cites work @@
+An improved exponential-time algorithm for             <i>k</i>             -SAT
+Normal rank
@@ Property / cites work @@
+A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
+Normal rank
@@ Property / cites work @@
+An algorithm for the satisfiability problem of formulas in conjunctive normal form
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank