Enumeration Reducibility with Polynomial Time

Abstract. We introduce polynomial time enumeration reducibility (≤pe) and we retrace Selman’s analysis of this reducibility and its relationship with non deterministic polynomial time conjunctive reducibility. We dis-cuss the basic properties of the degree structure induced by ≤pe over the computable sets and we show how to construct meets and joins. We are thus able to prove that this degree structure is dense and to show the existence of two types of lattice embeddings therein.