## 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 | |

State | Published - Oct 1988 |

## ASJC Scopus subject areas

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