The Isomorphism Conjecture Holds Relative to an Oracle

DOI10.1137/S0097539793248305MaRDI QIDQ4875451zbMATH OpenOpenAlexWikidataFDO

Authors Stuart A. Kurtz, S. Fenner, Lance Fortnow

Publication date 24 April 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793248305

zbMATH Keywords

Berman-Hartmanis isomorphism conjecturecomputational complexityisomorphism conjecturerelativization

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1256638
• The isomorphism conjecture fails relative to a random oracle
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• The isomorphism conjecture for NP
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• scientific article; zbMATH DE number 4154424
• An oracle separating conjectures about incompleteness in the finite domain
• scientific article; zbMATH DE number 4119621
• On relativizations with restricted number of accesses to the oracle set

Cited in

(8)

• Oracles for structural properties: The isomorphism problem and public-key cryptography
• A hierarchy based on output multiplicity
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• An oracle builder's toolkit
• Inverting onto functions.
• The isomorphism conjecture for NP
• scientific article; zbMATH DE number 1256638 (Why is no real title available?)
• The isomorphism conjecture for constant depth reductions

This page was built for publication: The Isomorphism Conjecture Holds Relative to an Oracle

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