The weak pigeonhole principle for function classes inS12

DOI10.1002/MALQ.200610015zbMATH Open1110.03054OpenAlexW2028894972MaRDI QIDQ3418087FDOQ3418087

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)