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

@@ Property / DOI @@
-.1007/s00037-013-0067-7
@@ Property / DOI: 10.1007/s00037-013-0067-7 / rank @@
-Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q17
@@ Property / Mathematics Subject Classification ID: 68Q17 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6189567
@@ Property / zbMATH DE Number: 6189567 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+satisfiability
@@ Property / zbMATH Keywords: satisfiability / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+exact algorithm
@@ Property / zbMATH Keywords: exact algorithm / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+formula
@@ Property / zbMATH Keywords: formula / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+parity gate
@@ Property / zbMATH Keywords: parity gate / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+average-case hardness
@@ Property / zbMATH Keywords: average-case hardness / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ 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
@@ Property / DOI @@
+.1007/S00037-013-0067-7
@@ Property / DOI: 10.1007/S00037-013-0067-7 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:354655