Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds (Q3012837): 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-22006-7_52
+Normal rank
@@ Property / OpenAlex ID @@
+W2279614198
@@ Property / OpenAlex ID: W2279614198 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
+Normal rank
@@ Property / cites work @@
+Mean-payoff games and propositional proofs
@@ Property / cites work: Mean-payoff games and propositional proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4850545
@@ Property / cites work: Q4850545 / rank @@
+Normal rank
@@ Property / cites work @@
+Non-automatizability of bounded-depth Frege proofs
+Normal rank
@@ Property / cites work @@
+On Interpolation and Automatization for Frege Systems
+Normal rank
@@ Property / cites work @@
+Polynomial size proofs of the propositional pigeonhole principle
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+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