5
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.