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

Original language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | IEEE Computer Society |

Pages | 380-389 |

Number of pages | 10 |

ISBN (Print) | 0818607408 |

State | Published - Dec 1 1986 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Fingerprint

### ASJC Scopus subject areas

- Hardware and Architecture

### Cite this

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 380-389). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE Computer Society.