scientific article; zbMATH DE number 1834646

zbMATH Open0999.03052MaRDI QIDQ4779142FDOQ4779142

Authors: Albert Atserias 

Publication date: 25 November 2002

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2136/21360148

Title of this publication is not available (Why is that?)

Recommendations

• Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
• Exponential lower bounds for the pigeonhole principle
• A new proof of the weak pigeonhole principle
• A new proof of the weak pigeonhole principle
• Provability of the pigeonhole principle and the existence of infinitely many primes

zbMATH Keywords

bounded arithmeticproof complexityweak pigeonhole principle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Cited In (6)

• Proving Infinitude of Prime Numbers Using Binomial Coefficients
• Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Iterated multiplication in \(VTC^0\)
• Propositional proof complexity
• A new proof of the weak pigeonhole principle

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4779142)