Abstract
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 |
| Pages | 126-131 |
| Number of pages | 6 |
| ISBN (Print) | 0818607947 |
| State | Published - 1987 |
| Externally published | Yes |
ASJC Scopus subject areas
- General Engineering