Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Enumeration reducibility with polynomial time bounds

Speaker: Charles Milton Harris
Slot: Array, 11:10-11:30, col. 1


We introduce polynomial time enumeration (pe-) reducibility and we retrace Selman's analysis of this reducibility and its relationship with non deterministic polynomial time conjunctive reducibility. We discuss the basic properties of the degree structure induced by pe-reducibility 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.

websites: Arnold Beckmann 2006-06-10