### Abstract

Summary form only given, as follows. L. Berman and H. Hartmanis (1977) conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (Karp complete) for NP. D. Joseph and P. Young (1985) discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the K_{f}^{k}'s) are not isomorphic to the standard NP-complete sets for some one-way functions f. These two conjectures cannot both be correct. The present authors introduce a new family of strong one-way functions, the scrambling functions. If f is a scrambling function, then K_{f}^{k} is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. In fact, if scrambling functions exist, then the isomorphism conjecture fails for essentially all natural complexity classes above NP, e.g., PSPACE, EXP, NEXP, and RE. As evidence for the existence of scrambling functions, much more powerful one-way functions--the annihilating functions--are shown to exist relative to a random oracle.

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

Title of host publication | Proc Struct Complexity Theor Fourth Ann Conf |

Editors | Anon |

Publisher | IEEE Computer Society |

Number of pages | 1 |

ISBN (Print) | 0818619589 |

State | Published - Dec 1 1989 |

Event | Proceedings: Structure in Complexity Theory - Fourth Annual Conference - Eugene, OR, USA Duration: Jun 19 1989 → Jun 22 1989 |

### Publication series

Name | Proc Struct Complexity Theor Fourth Ann Conf |
---|

### Other

Other | Proceedings: Structure in Complexity Theory - Fourth Annual Conference |
---|---|

City | Eugene, OR, USA |

Period | 6/19/89 → 6/22/89 |

### ASJC Scopus subject areas

- Engineering(all)

## Fingerprint Dive into the research topics of 'Isomorphism conjecture fails relative to a random oracle'. Together they form a unique fingerprint.

## Cite this

*Proc Struct Complexity Theor Fourth Ann Conf*(Proc Struct Complexity Theor Fourth Ann Conf). IEEE Computer Society.