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

DOI10.1006/JCSS.1997.1486zbMATH Open0888.68070OpenAlexW2146618200WikidataQ123230568 ScholiaQ123230568MaRDI QIDQ1362333FDOQ1362333

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

Recommendations

• One-way functions and the isomorphism conjecture
• The isomorphism conjecture fails relative to a random oracle
• The isomorphism conjecture for NP

zbMATH Keywords

oracleJoseph-Young conjecture

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• An oracle builder's toolkit
• The Isomorphism Conjecture Holds Relative to an Oracle
• Two queries
• A hierarchy based on output multiplicity
• Oracles for structural properties: The isomorphism problem and public-key cryptography

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362333)