Collapsing degrees

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

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

An m-degree is a collection of sets equivalent under polynomial-time many-one (Karp) reductions; for example, the complete sets for NP or PSPACE are m-degrees. An m-degree is collapsing iff its members are p-isomorphic, i.e., equivalent under polynomial-time, 1-1, onto, polynomial-time-invertible reductions. L. Berman and J. Hartmanis showed that all the then known NP-complete sets are isomorphic, and conjectured that the m-degree of the NP-complete sets collapses, in essence claiming that there is only one NP-complete set. However, until now no nontrivial collapsing m-degree was known to exist. In this paper we provide the first examples of such degrees. In particular, we show that there is a collapsing 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. We also obtain analogous results for noncollapsing degrees.

Original languageEnglish (US)
Pages (from-to)247-268
Number of pages22
JournalJournal of Computer and System Sciences
Volume37
Issue number2
DOIs
StatePublished - Oct 1988

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Collapsing degrees'. Together they form a unique fingerprint.

Cite this