The Isomorphism Conjecture Holds Relative to an Oracle

DOI10.1137/S0097539793248305zbMATH Open0841.68046OpenAlexW2118479312WikidataQ123118634 ScholiaQ123118634MaRDI QIDQ4875451FDOQ4875451

Lance Fortnow, Stuart A. Kurtz, S. Fenner

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)

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎
• An oracle separating conjectures about incompleteness in the finite domain 👍 👎
• Title not available (Why is that?) 👍 👎
• On relativizations with restricted number of accesses to the oracle set 👍 👎

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)