It has been conjectured that the m-degree of NP-complete sets collapses. Recent work has treated the conjecture more broadly and shown the existence of collapsing m-degrees and exhibited both collapsing and noncollapsing m-degrees that are 2-tt complete for EXP. It is shown here that recent constructions of collapsing degrees and noncollapsing degrees in EXP can be extended to: (1) ESPACE for Logspace reducibilities and isomorphisms; (2) SIGMA **p//2 for O(n**k)-time reducibilities and O(n**k** plus **1)-time isomorphism; and (3) 2-tt complete sets in NP**A for polynomial-time reducibilities for a sparse oracle A.
|Original language||English (US)|
|Title of host publication||Unknown Host Publication Title|
|Publisher||IEEE Computer Society|
|Number of pages||6|
|State||Published - Jan 1 1987|
ASJC Scopus subject areas