The polynomial and linear hierarchies in models where the weak pigeonhole principle fails

DOI10.2178/jsl/1208359061zbMath1141.03012OpenAlexW1978884179MaRDI QIDQ3503756

Neil Thapen, Leszek Aleksander Kołodziejczyk

Publication date: 9 June 2008

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1208359061

zbMATH Keywords

bounded arithmeticpolynomial hierarchymodels of arithmeticlinear hierarchy

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Models of arithmetic and set theory (03C62)

Related Items (4)

The polynomial and linear time hierarchies in V⁰ ⋮ A note on the Σ₁collection scheme and fragments of bounded arithmetic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Mathematical arguments in context

Cites Work

• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Multifunction algebras and the provability of \(PH\downarrow\)
• A model-theoretic characterization of the weak pigeonhole principle
• Structures interpretable in models of bounded arithmetic
• On the weak pigeonhole principle
• Provability of the pigeonhole principle and the existence of infinitely many primes
• On Independence of Variants of the Weak Pigeonhole Principle
• A new proof of the weak pigeonhole principle

This page was built for publication: The polynomial and linear hierarchies in models where the weak pigeonhole principle fails