Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Enumeration reducibility with polynomial time bounds

Speaker: Charles Milton Harris
Presentation: peTalk.pdf
Slot: Mon, 11:10-11:30, Faraday A (col. 1)

Abstract

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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net