Journal of Symbolic Logic 73 (2):578-592 (2008)

Abstract
We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S21 exists in which NP is not in the second level of the linear hierarchy; and that a model of S21 exists in which the polynomial hierarchy collapses to the linear hierarchy. Our methods are model-theoretic. We use the assumption about factoring to get a model in which the weak pigeonhole principle fails in a certain way, and then work with this failure to obtain our results. As a corollary of one of the proofs, we also show that in S21 the failure of WPHP (for Σb1 definable relations) implies that the strict version of PH does not collapse to a finite level
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1208359061
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,688
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Multifunction Algebras and the Provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
A Model-Theoretic Characterization of the Weak Pigeonhole Principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
Structures Interpretable in Models of Bounded Arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.

Add more references

Citations of this work BETA

Mathematical Arguments in Context.Jean Paul Van Bendegem & Bart Van Kerkhove - 2009 - Foundations of Science 14 (1-2):45-57.
The Polynomial and Linear Time Hierarchies in V0.Leszek A. Kołodziejczyk & Neil Thapen - 2009 - Mathematical Logic Quarterly 55 (5):509-514.

Add more citations

Similar books and articles

Analytics

Added to PP index
2010-08-24

Total views
21 ( #473,313 of 2,349,560 )

Recent downloads (6 months)
1 ( #510,673 of 2,349,560 )

How can I increase my downloads?

Downloads

My notes