PROGRESS ON COLLAPSING DEGREES.

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

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

ASJC Scopus subject areas

  • Engineering(all)

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

Cite this