8
$\begingroup$

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic ($p$-isomorphic) to each other. It has been an early attempt (published in 1977) to prove $P\neq NP$. It is still open, and if true, it indeed implies $P\neq NP$.

However, the proof of this implication is essentially trivial: it is proved by referring to the fact that if $P=NP$, then there are finite $NP$-complete languages, which clearly contradicts to the Isomorphism Conjecture, since a finite language cannot be $p$-isomorphic to SAT.

While the above proof is technically correct, I find it somehow disturbing that to prove the implication one needs a finite $NP$-complete language.

Question: Let us consider a weaker version of the conjecture, stating only that all infinite $NP$-complete languages are $p$-isomorphic. Would this still imply $P\neq NP$? Is anything known about this weaker version of the conjecture?

$\endgroup$
  • 5
    $\begingroup$ The Wikipedia article on the conjecture outlines an argument that uses sparsity in lieu of finiteness, but is otherwise essentially the same. Perhaps weaken the conjecture further, to state only that sufficiently dense $\mathsf{NP}$-complete languages are isomorphic? "Sufficiently dense" in this case means that density/sparsity considerations don't eliminate an isomorphism with SAT. $\endgroup$ – Andrew Morgan Sep 19 '16 at 5:33
  • 3
    $\begingroup$ Perhaps this works: if $P=NP$ then $A = \{2 \uparrow \uparrow n \}$ (towers of 2) is NPC (just solve the NP problem using the polynomial time algorithm and map to $1 \notin A$ or $2 \in A$ ) but $A$ cannot be p-isomorphic to SAT. So also the weaker conjecture implies $P \neq NP$ $\endgroup$ – Marzio De Biasi Sep 19 '16 at 8:34
  • 2
    $\begingroup$ @AndrewMorgan : ​ (I don't know if "density/sparsity" means you already realize this, but) $\hspace{.95 in}$ One would need to require density of the complement too. ​ ​ ​ ​ $\endgroup$ – user6973 Sep 19 '16 at 9:04
  • $\begingroup$ Yes, it indeed seems that the "right" version of the weaker conjecture is this: all NP-complete languages with exponential density and co-density are p-isomorphic. (This density requirement means that there is a constant $c>0$, such that both the language and its complement contains $\geq 2^{cn}$ $n$-bit strings for every $n$.) $\endgroup$ – Andras Farago Sep 20 '16 at 14:54
  • $\begingroup$ That's much stronger than should be necessary: ​ ​ ​ ​ ​ ​ ​ "≥ 2^(n^c) ​ (<n)-bit strings for all sufficiently large n" ​ ​ ​ should be enough. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user6973 Sep 21 '16 at 0:53

Your Answer

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

Browse other questions tagged or ask your own question.