Satisfiability Certificates Verifiable in Subexponential Time (Q3007671): 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.1007/978-3-642-21581-0_4
+Normal rank
@@ Property / OpenAlex ID @@
+W1480076195
@@ Property / OpenAlex ID: W1480076195 / 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 @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+A full derandomization of schöning's k-SAT algorithm
+Normal rank
@@ Property / cites work @@
+On the complexity of circuit satisfiability
@@ Property / cites work: On the complexity of circuit satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+An improved exponential-time algorithm for             <i>k</i>             -SAT
+Normal rank
@@ Property / cites work @@
+Q4484662
@@ Property / cites work: Q4484662 / rank @@
+Normal rank
@@ Property / cites work @@
+An algorithm for the satisfiability problem of formulas in conjunctive normal form
+Normal rank
@@ Property / cites work @@
+Improving exhaustive search implies superpolynomial lower bounds
+Normal rank