The isomorphism conjecture holds and one-way functions exist relative to an oracle

DOI10.1006/jcss.1997.1486zbMath0888.68070OpenAlexW2146618200WikidataQ123230568 ScholiaQ123230568MaRDI QIDQ1362333

O. Diekmann

Publication date: 13 May 1998

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1486

zbMATH Keywords

oracleJoseph-Young conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (4)

An oracle builder's toolkit ⋮ Two queries ⋮ A hierarchy based on output multiplicity ⋮ Reductions in circuit complexity: An isomorphism theorem and a gap theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On one-way functions and polynomial-time isomorphisms
• An oracle builder's toolkit
• One-way functions and the nonisomorphism of NP-complete sets
• Relativizations of Unambiguous and Random Polynomial Time Classes
• Complexity Measures for Public-Key Cryptosystems
• Relativized Questions Involving Probabilistic Algorithms
• A survey of one-way functions in complexity theory
• Complete Problems and Strong Polynomial Reducibilities
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The isomorphism conjecture fails relative to a random oracle
• The Isomorphism Conjecture Holds Relative to an Oracle

This page was built for publication: The isomorphism conjecture holds and one-way functions exist relative to an oracle