Relativized isomorphisms of NP-complete sets

In this paper, we present several results about collapsing and non-collapsing degrees ofNP-complete sets. The first, a relativized collapsing result, is interesting because it is the strongest known constructive approximation to a relativization of Berman and Hartmanis' 1977 conjecture that all _m^P-complete sets forNP arep-isomorphic. In addition, the collapsing result explores new territory in oracle construction, particularly in combining overlapping and apparently incompatible coding and diagonalizing techniques. We also present non-collapsing results, which are notable for their technical simplicity, and which rely on no unproven assumptions such as one-way functions. The basic technique developed in these non-collapsing constructions is surprisingly robust, and can be combined with many different oracle constructions.