On computational complexity and honest polynomial degrees

AbstractIt is shown that no Δ20 set A with A and A both semilow has minimal honest polynomial (hp)-degree. The technique extends to show that the hp-degrees and polynomial degrees of low r.e. sets are dense. In particular, r.e. sets of minimal hp-degree must have high computational complexity in the sense of Blum and Marques (J. Symbolic Logic 38 (1973) 579–593). These results also hold for tally degrees and polynomial (honest) m-degrees