Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e‐reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non‐deterministic polynomial time reducibility. We define the polynomial time e‐degrees as the equivalence classes under this reducibility and investigate their structure on the recursive (...) sets, showing in particular that the pe‐degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy. (shrink)

We discuss a notion of forcing that characterizes enumeration 1-genericity, and we investigate the immunity, lowness, and quasiminimality properties of enumeration 1-generic sets and their degrees. We construct an enumeration operator Δ such that, for any A, the set ΔA is enumeration 1-generic and has the same jump complexity as A. We deduce from this and other recent results from the literature that not only does every degree a bound an enumeration 1-generic degree b such that a'=b', but also that, (...) if a is nonzero, then we can find such b satisfying 0eshrink)

We compare the degrees of enumerability and the closed Medvedev degrees and find that many situations occur. There are nonzero closed degrees that do not bound nonzero degrees of enumerability, there are nonzero degrees of enumerability that do not bound nonzero closed degrees, and there are degrees that are nontrivially both degrees of enumerability and closed degrees. We also show that the compact degrees of enumerability exactly correspond to the cototal enumeration degrees.

We show that every nonzero $${\Delta^{0}_{2}}$$ enumeration degree bounds the enumeration degree of a 1-generic set. We also point out that the enumeration degrees of 1-generic sets, below the first jump, are not downwards closed, thus answering a question of Cooper.