Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Research output: Chapter in Book/Entry/PoemConference contribution

9 Scopus citations


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 languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherIEEE Computer Society
Number of pages6
ISBN (Print)0818607947
StatePublished - 1987
Externally publishedYes

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'PROGRESS ON COLLAPSING DEGREES.'. Together they form a unique fingerprint.

Cite this