Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture :
All $NP$-Complete languages are $p$-isomorphic.
Then the book says that if the conjecture is True then $P \ne NP$. I am unable to make sense of the proof the book gives, which is:
If $P=NP$ then all languages in $P$ are $NP$-Complete, but there are finite languages in $P$ and these cannot be $p$-isomorphic to infinite languages.
Two languages $X$ and $Y$ are $p$-isomorphic if there's a polynomial-time computable bijection $f\colon X\to Y$ such that $w\in X\iff f(w)\in Y$.
Now, suppose that P$\,=\,$NP. Assuming we're defining NP-completeness in terms of polynomial-time many-one reductions, every language in NP, except for $\emptyset$ and $\Sigma^*$ is NP-complete. To see this, let $Y\in\mathbf{NP}\setminus\{\emptyset, \Sigma^*\}$ and pick two strings $w_{\mathrm{in}}\in Y$ and $w_{\mathrm{out}}\notin Y$. For any language $X\in \mathbf{NP}$, we can reduce $X$ to $Y$ in polynomial time using the function $$f(w) = \begin{cases} \,w_{\mathrm{in}} &\text{if }w\in X\\ \,w_{\mathrm{out}} &\text{if }w\notin X\,. \end{cases}$$ Since $X$ can be decided in polynomial time, we can compute $f$ in polynomial time. Note that there is a small error in the proof quoted in the question, which claims that all languages in P would be NP-complete if P$\,=\,$NP. This is incorrect: if we took $Y=\emptyset$ or $Y=\Sigma^*$, the reduction wouldn't work because one of $w_{\mathrm{in}}$ and $w_{\mathrm{out}}$ wouldn't exist.
So, we've established that, if P$\,=\,$NP, then every finite language is NP-complete; we also know that some infinite languages, such as $\mathrm{SAT}$ are NP-complete. But now suppose that there's a $p$-isomorphism between every pair of NP-complete languages. That means that, in particular, there's a bijection between every finite language and $\mathrm{SAT}$. But there can't be a bijection between a finite set and an infinite set.
