Collapsing degrees

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

doi:10.1016/0022-0000(88)90007-4

Collapsing degrees

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

Research output: Contribution to journal › Article › peer-review

14 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 language	English (US)
Pages (from-to)	247-268
Number of pages	22
Journal	Journal of Computer and System Sciences
Volume	37
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(88)90007-4
State	Published - Oct 1988
Externally published	Yes

ASJC Scopus subject areas

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

Access to Document

10.1016/0022-0000(88)90007-4

Cite this

@article{0359cf1c8d6f4eb8887acf952bb0ce6f,

title = "Collapsing degrees",

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.",

author = "Kurtz, {Stuart A.} and Mahaney, {Stephen R.} and Royer, {James S.}",

note = "Funding Information: * Research supported in part by NSF Grant DCR-8602562. t Research supported in part by NSF Grant DCR-8602991.",

year = "1988",

month = oct,

doi = "10.1016/0022-0000(88)90007-4",

language = "English (US)",

volume = "37",

pages = "247--268",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Collapsing degrees

AU - Kurtz, Stuart A.

AU - Mahaney, Stephen R.

AU - Royer, James S.

N1 - Funding Information: * Research supported in part by NSF Grant DCR-8602562. t Research supported in part by NSF Grant DCR-8602991.

PY - 1988/10

Y1 - 1988/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0013002849&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013002849&partnerID=8YFLogxK

U2 - 10.1016/0022-0000(88)90007-4

DO - 10.1016/0022-0000(88)90007-4

M3 - Article

AN - SCOPUS:0013002849

SN - 0022-0000

VL - 37

SP - 247

EP - 268

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Collapsing degrees

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this