The isomorphism conjecture fails relative to a random oracle
From MaRDI portal
Publication:4369869
DOI10.1145/201019.201030zbMath0886.68068OpenAlexW2090039082WikidataQ56610697 ScholiaQ56610697MaRDI QIDQ4369869
Stephen R. Mahaney, Stuart A. Kurtz, James S. Royer
Publication date: 2 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://surface.syr.edu/eecs/37
Related Items
The random oracle hypothesis is false, Collapsing degrees via strong computation, Structural complexity theory: Recent surprises, One-way functions and the nonisomorphism of NP-complete sets, Simultaneous strong separations of probabilistic and unambiguous complexity classes, DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization, The isomorphism conjecture holds and one-way functions exist relative to an oracle, On P-immunity of exponential time complete sets, A survey of one-way functions in complexity theory, The degree structure of 1-L reductions, The isomorphism conjecture for constant depth reductions, An oracle builder's toolkit, Polynomial-time axioms of choice and polynomial-time cardinality, Non-uniform reductions, Inverting onto functions., On the topological size of p-m-complete degrees, Oracles for structural properties: The isomorphism problem and public-key cryptography, Relativized isomorphisms of NP-complete sets, Circuit size relative to pseudorandom oracles, Reductions to sets of low information content, A hierarchy based on output multiplicity, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, Relativized worlds with an infinite hierarchy
