Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms (Q1401230): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of the pigeonhole principle
@@ Property / cites work: The complexity of the pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial principles in elementary number theory
+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 @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Time-space tradeoffs for satisfiability
@@ Property / cites work: Time-space tradeoffs for satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Q3962995
@@ Property / cites work: Q3962995 / rank @@
+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 @@
+Q4535013
@@ Property / cites work: Q4535013 / rank @@
+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 @@
+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 @@
+Primes and their residue rings in models of open induction
+Normal rank
@@ Property / cites work @@
+Q5628106
@@ Property / cites work: Q5628106 / rank @@
+Normal rank
@@ Property / cites work @@
+Provability of the pigeonhole principle and the existence of infinitely many primes
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for the weak pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for perfect matching principles
+Normal rank
@@ Property / cites work @@
+Proof theory. 2nd ed
@@ Property / cites work: Proof theory. 2nd ed / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0304-3975(02)00394-8
+Normal rank
@@ Property / OpenAlex ID @@
+W1503753783
@@ Property / OpenAlex ID: W1503753783 / rank @@
+Normal rank