On The Topological Size of p-m-Complete Degrees

All polynomial many-one degrees are shown to be of second Baire category in the superset topology when witness functions are allowed to run in 2 log h n time, for any h. Any improvement of this result for the complete p-m-degrees of RE, EXP or NP implies P<F NaN> 6= NP. 1 Introduction Understanding the properties of complete degrees is a central theme of research in complexity theory. Questions like ffl Are complete sets p-creative for P ? ffl Are all complete sets paddable ? Are they self-reducible ? ffl Do all complete sets contain infinite polynomial time sets ? ffl Which are the collapsing complete degrees, i.e., degrees consisting of only one p-isomorphism type ? have direct, decisive implications on the relation between the most important complexity classes. Kurtz, Mahaney and Royer have written an excellent survey of these topics [KMR90]. In this work we pursue the study of the topological size of some interesting classes of sets begun in [Zim93], focusing this time on c..