Relativized isomorphisms of NP-complete sets

Judy Goldsmith, Deborah Joseph

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


In this paper, we present several results about collapsing and non-collapsing degrees of NP-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 ≤mP-complete sets for NP are p-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.

Original languageEnglish
Pages (from-to)186-205
Number of pages20
JournalComputational Complexity
Issue number2
StatePublished - Jun 1993


  • collapsing degrees
  • complexity classes
  • isomorphisms
  • NP-completeness
  • relativized computation
  • sparse oracles
  • Subject classifications: 68Q15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Mathematics (all)
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Relativized isomorphisms of NP-complete sets'. Together they form a unique fingerprint.

Cite this