The structure of the honest polynomial m-degrees

Annals of Pure and Applied Logic 70 (2):113-139 (1994)

Abstract
We prove a number of structural theorems about the honest polynomial m-degrees contingent on the assumption P = NP . In particular, we show that if P = NP , then the topped finite initial segments of Hm are exactly the topped finite distributive lattices, the topped initial segments of Hm are exactly the direct limits of ascending sequences of finite distributive lattices, and all recursively presentable distributive lattices are initial segments of Hm ∩ RE. Additionally, assuming ¦∑¦ = 1, we show that the theory of the hpm-degrees is undecidable. We also show that index sets cannot be minimal. Lastly, we examine an alternative definition of honest m-reduction under which recursive minimal sets can be constructed
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(94)90027-2
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,824
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

Distributive Initial Segments of the Degrees of Unsolvability.A. H. Lachlan - 1968 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (30):457-472.
Distributive Initial Segments of the Degrees of Unsolvability.A. H. Lachlan - 1968 - Mathematical Logic Quarterly 14 (30):457-472.
A Classification of the Recursive Functions.Albert R. Meyer & Dennis M. Ritchie - 1972 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 18 (4-6):71-82.
A Classification of the Recursive Functions.Albert R. Meyer & Dennis M. Ritchie - 1972 - Mathematical Logic Quarterly 18 (4‐6):71-82.

View all 7 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

A Jump Operator on Honest Subrecursive Degrees.Lars Kristiansen - 1998 - Archive for Mathematical Logic 37 (2):105-125.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
The Jump Operation for Structure Degrees.V. Baleva - 2006 - Archive for Mathematical Logic 45 (3):249-265.
On Downey's Conjecture.Marat M. Arslanov, Iskander Sh Kalimullin & Steffen Lempp - 2010 - Journal of Symbolic Logic 75 (2):401-441.
On Defining Truth.Frank Deaver - 1990 - Journal of Mass Media Ethics 5 (3):168 – 177.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
Degrees of Continuous Functionals.Peter G. Hinman - 1973 - Journal of Symbolic Logic 38 (3):393-395.
Infima of D.R.E. Degrees.Jiang Liu, Shenling Wang & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (1):35-49.
On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.

Analytics

Added to PP index
2014-01-16

Total views
22 ( #435,696 of 2,309,317 )

Recent downloads (6 months)
1 ( #761,345 of 2,309,317 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature