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

}