The weak pigeonhole principle for function classes inS12

DOI10.1002/MALQ.200610015MaRDI QIDQ3418087zbMATH OpenOpenAlexFDO

Authors Norman Danner, Chris Pollett

Publication date 2 February 2007

Published in MLQ (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200610015

zbMATH Keywords

bounded arithmeticweak pigeonhole principle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• Circuit principles and weak pigeonhole variants
• On the weak pigeonhole principle
• A model-theoretic characterization of the weak pigeonhole principle
• On Independence of Variants of the Weak Pigeonhole Principle
• A new proof of the weak pigeonhole principle

Cites work

• scientific article; zbMATH DE number 806747 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• On the bounded version of Hilbert's tenth problem

Cited in

(2)

• On Independence of Variants of the Weak Pigeonhole Principle
• Circuit principles and weak pigeonhole variants

This page was built for publication: The weak pigeonhole principle for function classes inS12

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