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