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

computational complexityisomorphism conjecturerelativizationBerman-Hartmanis isomorphism conjecture

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
• Publication:4733402
• On relativizations with restricted number of accesses to the oracle set

Cited in

(7)

• An oracle builder's toolkit
• The isomorphism conjecture for NP
• A hierarchy based on output multiplicity
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• Inverting onto functions.
• 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)