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

Research output: Chapter in Book/Entry/PoemConference contribution

8 Scopus citations


An m-degree is a collection of sets equivalent under polynomial-time many-one (Karp) reductions. An m-degree is collapsing if its members are p-isomorphic, i. e. , equivalent under polynomial time, 1-1, onto polynomial-time invertible reductions. L. Berman and J. Hartmanis (1977) showed that all the then known natural NP-complete sets are isomorphic, and conjectured that the m-degree of the NP-complete sets collapses, is essence claiming that there is only one NP-complete set. The authors present the first examples of nontrivial collapsing m-degrees. They slow that there is a collapsible degree which is btt-complete for EXP (the exponential-time decidable sets) and that for every set A there is a collapsing degree which is hard for A.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE Computer Society
Number of pages10
ISBN (Print)0818607408, 9780818607400
StatePublished - 1986
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture


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

Cite this