A satisfiability algorithm and average-case hardness for formulas over the full binary basis (Q354655): Difference between revisions

@@ Property / OpenAlex ID @@
+W2104306727
@@ Property / OpenAlex ID: W2104306727 / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
+Normal rank
@@ Property / cites work @@
+Algorithms and Computation
@@ Property / cites work: Algorithms and Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Q5503674
@@ Property / cites work: Q5503674 / rank @@
+Normal rank
@@ Property / cites work @@
+On the construction of affine extractors
@@ Property / cites work: On the construction of affine extractors / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Satisfiability of Small Depth Circuits
+Normal rank
@@ Property / cites work @@
+An improved exponential-time algorithm for             <i>k</i>             -SAT
+Normal rank
@@ Property / cites work @@
+STACS 2004
@@ Property / cites work: STACS 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+The effect of random restrictions on formula size
@@ Property / cites work: The effect of random restrictions on formula size / rank @@
+Normal rank
@@ Property / cites work @@
+The Shrinkage Exponent of de Morgan Formulas is 2
@@ Property / cites work: The Shrinkage Exponent of de Morgan Formulas is 2 / rank @@
+Normal rank
@@ Property / cites work @@
+-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
+Normal rank
@@ Property / cites work @@
+Q3281059
@@ Property / cites work: Q3281059 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743451
@@ Property / cites work: Q5743451 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Hardness against Constant-Depth Linear-Size Circuits
+Normal rank
@@ Property / cites work @@
+Derandomizing the HSSW algorithm for 3-SAT
@@ Property / cites work: Derandomizing the HSSW algorithm for 3-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Solving satisfiability in less than \(2^ n\) steps
+Normal rank
@@ Property / cites work @@
+A full derandomization of schöning's k-SAT algorithm
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Q4484662
@@ Property / cites work: Q4484662 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4218095
@@ Property / cites work: Q4218095 / 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
@@ Property / cites work @@
+Affine extractors over prime fields
@@ Property / cites work: Affine extractors over prime fields / rank @@
+Normal rank