Lower bounds for the weak pigeonhole principle and random formulas beyond resolution (Q1854546): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2041857712
@@ Property / OpenAlex ID: W2041857712 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q60512223
@@ Property / Wikidata QID: Q60512223 / rank @@
+Normal rank
@@ Property / cites work @@
+The monotone circuit complexity of Boolean functions
+Normal rank
@@ Property / cites work @@
+The Efficiency of Resolution and Davis--Putnam Procedures
+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 @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+Q4218929
@@ Property / cites work: Q4218929 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial size proofs of the propositional pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Resolution proofs of generalized pigeonhole principles
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q3956129
@@ Property / cites work: Q3956129 / rank @@
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / 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 @@
+A new proof of the weak pigeonhole principle
@@ Property / cites work: A new proof of the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Provability of the pigeonhole principle and the existence of infinitely many primes
+Normal rank
@@ Property / cites work @@
+Regular resolution lower bounds for the weak pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for the weak pigeonhole principle
+Normal rank