Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies (Q2500481): Difference between revisions

@@ Property / cites work @@
+The independence of the modulo <i>p</i> counting principles
+Normal rank
@@ Property / cites work @@
+The relative complexity of NP search problems
@@ Property / cites work: The relative complexity of NP search problems / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
+Normal rank
@@ Property / cites work @@
+An exponential separation between the parity principle and the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+On Interpolation and Automatization for Frege Systems
+Normal rank
@@ Property / cites work @@
+Hex Strategy
@@ Property / cites work: Hex Strategy / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial size proofs of the propositional pigeonhole principle
+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 @@
+Linear gaps between degrees for the polynomial calculus modulo distinct primes
+Normal rank
@@ Property / cites work @@
+Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+The Game of Hex and the Brouwer Fixed-Point Theorem
+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 @@
+An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q4135772
@@ Property / cites work: Q4135772 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of the parity argument and other inefficient proofs of existence
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank