Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
type: Item
instance of: scholarly article
title: Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
zbMATH Open document ID: 1017.03034
DOI: 10.1016/S0304-3975(02)00394-8
author: Albert Atserias
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 1965264
zbMATH Keywords: weak pigeonhole principle
zbMATH Keywords: bounded-depth Frege
zbMATH Keywords: bounded arithmetic
MaRDI profile type: Publication
cites work: The complexity of the pigeonhole principle
cites work: Combinatorial principles in elementary number theory
cites work: Polynomial size proofs of the propositional pigeonhole principle
cites work: Resolution proofs of generalized pigeonhole principles
cites work: The relative efficiency of propositional proof systems
cites work: Time-space tradeoffs for satisfiability
cites work: Q3962995
cites work: Q5286672
cites work: The intractability of resolution
cites work: Q4535013
cites work: Q4856172
cites work: An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
cites work: A new proof of the weak pigeonhole principle
cites work: Primes and their residue rings in models of open induction
cites work: Q5628106
cites work: Provability of the pigeonhole principle and the existence of infinitely many primes
cites work: Exponential lower bounds for the pigeonhole principle
cites work: Resolution lower bounds for the weak pigeonhole principle
cites work: Resolution lower bounds for perfect matching principles
cites work: Proof theory. 2nd ed
full work available at URL: s0304-3975(02)00394-8
OpenAlex ID: W1503753783
description: scientific article; zbMATH DE number 1965264