The central premise of the theory of NP-completeness asserts that it is no coincidence that most important problems fall into two categories: those with efficient algorithms, and those that are NP-complete. (If P = NP, then these two are but one category, violating this premise.) Two decades ago, the Berman-Hartmanis conjecture took this premise one step further, asserting that the NP-complete sets are all isomorphic, being simple re-encodings of one another. More recently, popular conjectures have gone the other way, asserting that an encrypted version of SAT should not be isomorphic to SAT. A large body of work is devoted to this topic, and this paper contains an excellent overview.

This paper contains the first results showing that a certain kind of one-way function is sufficient to produce nonisomorphic NP-complete sets. Furthermore, it argues that such one-way functions are likely to exist, and in fact they do exist relative to random oracles. Thus, relative to random oracles, the complete sets are not all isomorphic. This is true for NP as well as for most other complexity classes of interest.

“Random oracle” results (and relativization results, in general) have been the source of some controversy, and there is insufficient space here to discuss this in depth. The paper contains an excellent discussion of random oracle results in general, and how one should interpret this result in particular.

The paper is well written, the proofs are clear, and the story the authors tell is interesting.