COLLAPSING DEGREES.

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

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

8 Scopus citations

Abstract

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
Pages380-389
Number of pages10
ISBN (Print)0818607408
StatePublished - Dec 1 1986

Publication series

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

    Fingerprint

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this

Kurtz, S. A., Mahaney, S. R., & Royer, J. S. (1986). COLLAPSING DEGREES. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 380-389). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE Computer Society.