### Abstract

L. Berman and J. Hartmanis conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete ('Karp' complete) for NP. D. Joseph and P. Young discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets are not isomorphic to the standard NP-complete sets for some one-way functions f. These two conjectures cannot both be correct. We introduce a new family of strong one-way functions, the scrambling functions. If f is a scrambling function, then the above mentioned sets are not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. As evidence for the existence of scrambling functions, we show that much more powerful one-way functions, the annihilating functions, exist relative to a random oracle.

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

Title of host publication | Proc Twenty First Annu ACM Symp Theory Comput |

Publisher | Publ by ACM |

Pages | 157-166 |

Number of pages | 10 |

ISBN (Print) | 0897913078 |

State | Published - Dec 1 1989 |

Event | Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA Duration: May 15 1989 → May 17 1989 |

### Publication series

Name | Proc Twenty First Annu ACM Symp Theory Comput |
---|

### Other

Other | Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing |
---|---|

City | Seattle, WA, USA |

Period | 5/15/89 → 5/17/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 Twenty First Annu ACM Symp Theory Comput*(pp. 157-166). (Proc Twenty First Annu ACM Symp Theory Comput). Publ by ACM.