THE ISOMORPHISM CONJECTURE HOLDS RELATIVE TO AN ORACLE

The authors introduce symmetric perfect generic sets. These sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. We then show that the Berman-Hartmanis isomorphism conjec ture holds relative to any sp-generic oracle, i.e., for any symmetric perfect generic set A, all NPA-complete sets are polynomial-time isomo rphic relative to A. Prior to this work, there were no known oracles r elative to which the isomorphism conjecture held. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect g eneric sets, it is also shown that P-A=FewP(A) for any symmetric perfe ct generic A.