The Berman-Hartmanis Isomorphism Conjecture states that all NP-complete sets are polynomial-time isomorphic to each other. The conjecture is still open.

Let Σ

^{n}be the set of all strings of length n and Σ

^{≤n}be the set of all strings of length at most n.

We say a set S is dense if for some ε>0, |S∩Σ

^{≤n}| ≥ 2

^{nε}for all n. A set S is sparse if for some c, |S∩Σ

^{n}|≤ n

^{c}. Every finite set is sparse and no dense set is sparse.

We showed in class that if the Berman-Hartmanis conjecture is true then every NP-complete set is dense. In paticular under this assumption there are no sparse or finite NP-complete sets and P ≠ NP.

The Berman-Hartmanis conjecture remains open but Mahaney proved the following: If there is a sparse NP-complete set then P = NP. In class we gave the proof of Ogihara and Watanabe which I also wrote up in my blog.