The structure of the honest polynomial m-degrees

AbstractWe prove a number of structural theorems about the honest polynomial m-degrees (denoted by Hm or hpm-degrees) contingent on the assumption P = NP (or a unary alphabet). In particular, we show that if P = NP (or a unary alphabet), 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