Short propositional refutations for dense random 3CNF formulas (Q741088): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.apal.2014.08.001
+Normal rank
@@ Property / OpenAlex ID @@
+W2950542447
@@ Property / OpenAlex ID: W2950542447 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for k-DNF resolution on random 3-CNFs
+Normal rank
@@ Property / cites work @@
+Resolution Is Not Automatizable Unless W[P] Is Tractable
+Normal rank
@@ Property / cites work @@
+Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
+Normal rank
@@ Property / cites work @@
+The Efficiency of Resolution and Davis--Putnam Procedures
+Normal rank
@@ Property / cites work @@
+Random CNF's are hard for the polynomial calculus
@@ Property / cites work: Random CNF's are hard for the polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+On Interpolation and Automatization for Frege Systems
+Normal rank
@@ Property / cites work @@
+Q3794177
@@ Property / cites work: Q3794177 / rank @@
+Normal rank
@@ Property / cites work @@
+Cutting planes, connectivity, and threshold logic
@@ Property / cites work: Cutting planes, connectivity, and threshold logic / rank @@
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5465359
@@ Property / cites work: Q5465359 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5306365
@@ Property / cites work: Q5306365 / rank @@
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+A Computing Procedure for Quantification Theory
@@ Property / cites work: A Computing Procedure for Quantification Theory / rank @@
+Normal rank
@@ Property / cites work @@
+A machine program for theorem-proving
@@ Property / cites work: A machine program for theorem-proving / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002778
@@ Property / cites work: Q3002778 / rank @@
+Normal rank
@@ Property / cites work @@
+Recognizing More Unsatisfiable Random <i>k</i>-SAT Instances Efficiently
+Normal rank
@@ Property / cites work @@
+Optimality of size-degree tradeoffs for polynomial calculus
+Normal rank
@@ Property / cites work @@
+Q2762790
@@ Property / cites work: Q2762790 / rank @@
+Normal rank
@@ Property / cites work @@
+Recognizing more random unsatisfiable 3-SAT instances efficiently
+Normal rank
@@ Property / cites work @@
+Q5286672
@@ Property / cites work: Q5286672 / rank @@
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Matrix Analysis
@@ Property / cites work: Matrix Analysis / rank @@
+Normal rank
@@ Property / cites work @@
+Short proofs for the determinant identities
@@ Property / cites work: Short proofs for the determinant identities / rank @@
+Normal rank
@@ Property / cites work @@
+Dual weak pigeonhole principle, Boolean complexity, and derandomization
+Normal rank
@@ Property / cites work @@
+Lower bounds to the size of constant-depth propositional proofs
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+On the weak pigeonhole principle
@@ Property / cites work: On the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD <font>NP</font> ∩ <font>coNP</font> FUNCTION
+Normal rank
@@ Property / cites work @@
+Q4527041
@@ Property / cites work: Q4527041 / rank @@
+Normal rank
@@ Property / cites work @@
+Short Propositional Refutations for Dense Random 3CNF Formulas
+Normal rank
@@ Property / cites work @@
+Proving Infinitude of Prime Numbers Using Binomial Coefficients
+Normal rank
@@ Property / cites work @@
+Theories for TC0 and Other Small Complexity Classes
+Normal rank
@@ Property / cites work @@
+Q4152212
@@ Property / cites work: Q4152212 / rank @@
+Normal rank
@@ Property / cites work @@
+A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution
+Normal rank
@@ Property / cites work @@
+The proof complexity of linear algebra
@@ Property / cites work: The proof complexity of linear algebra / rank @@
+Normal rank
@@ Property / cites work @@
+Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem
+Normal rank
@@ Property / cites work @@
+Notes on polynomially bounded arithmetic
@@ Property / cites work: Notes on polynomially bounded arithmetic / rank @@
+Normal rank