Collapsing degrees in subexponential time
Deborah Joseph, Randall J. Pruim, P. Young · 2002
We show that there are subexponential deterministic time classes that have collapsing degrees. In particular, we prove the following: Let t be any effectively superpolynomial time bound. Then there is a set A/spl isin/DTIME(t) such that every set B/spl isin/deg/sub msup p/(A) is p-isomorphic to A.>