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

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,694

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2014-01-16

Downloads
23 (#497,762)

6 months
1 (#388,311)

Historical graph of downloads
How can I increase my downloads?

References found in this work

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

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 - 2005 - 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.