@inproceedings{a54d16824b1d4f119c0e8beffca21d75,
title = "COLLAPSING DEGREES.",
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.",
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 = "1986",
doi = "10.1109/sfcs.1986.13",
language = "English (US)",
isbn = "0818607408",
series = "Annual Symposium on Foundations of Computer Science (Proceedings)",
publisher = "IEEE Computer Society",
pages = "380--389",
booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",
address = "United States",
}