Computability in Europe 2006
Logical Approaches to Computational Barriers
|Speaker:||Charles Milton Harris|
|Slot:||Mon, 11:10-11:30, Faraday A (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|