Assignment 1, due Monday, September 18, has been posted on T-Square. I highly recommend you start thinking about the problems immediately.
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| ≥ 2nε for all n. A set S is sparse if for some c, |S∩Σn|≤ nc. 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.
