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}| ≥ 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.