Collapsing degrees

摘要

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.