scientific article; zbMATH DE number 1834646

MaRDI QIDQ4779142zbMATH OpenFDO

Authors Albert Atserias

Publication date 25 November 2002

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

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)

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

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)