<p>The famous <a href="http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture">Isomorphism Conjecture of Berman and Hartmanis</a> 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$. </p>

<p>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.</p>

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

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

CC BY-SA 3.0
2016-09-19T05:33:14.740Z
The [Wikipedia article](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture#Implications) 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.
Andrew Morgan
CC BY-SA 3.0
2016-09-19T08:34:24.340Z
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$
Marzio De Biasi
CC BY-SA 3.0
2016-09-20T14:54:41.483Z
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$.)
Andras Farago
CC BY-SA 4.0
2019-10-17T16:05:29.257Z
It's enough to have two exp. dense and co-dense sets in P that aren't p-isomorphic. Here's a thought: take two non-isomorphic exp. dense sets L,L' in P (shouldn't be too hard to find). Consider $L_1 = L \oplus \overline{L} = \{(0,x) : x \in L\} \cup \{(1,y) : y \notin L\}$ and $L_2 = L \oplus \overline{L}'$. Both $L_1,L_2$ are now exp. dense *and* co-dense, and in P. I don't immediately see how to show that they aren't isomorphic, but it seems like one might be able to get that with a little extra work/diagonalization. If I have time I'll try to work it out...
Joshua Grochow
<cc.complexity-theory><np-complete><p-vs-np>
What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?
Andras Farago
# What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

(Asked by: username_0 on 2016-09-19)

The famous [Isomorphism Conjecture of Berman and Hartmanis](http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture) 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?

**Tags:** cc.complexity-theory, np-complete, p-vs-np

> **Comments:**
> **username_1**: The [Wikipedia article](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture#Implications) 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.  
> **username_2**: 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$  
> **username_0**: 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$.)  
> **username_3**: It's enough to have two exp. dense and co-dense sets in P that aren't p-isomorphic. Here's a thought: take two non-isomorphic exp. dense sets L,L' in P (shouldn't be too hard to find). Consider $L_1 = L \oplus \overline{L} = \{(0,x) : x \in L\} \cup \{(1,y) : y \notin L\}$ and $L_2 = L \oplus \overline{L}'$. Both $L_1,L_2$ are now exp. dense *and* co-dense, and in P. I don't immediately see how to show that they aren't isomorphic, but it seems like one might be able to get that with a little extra work/diagonalization. If I have time I'll try to work it out...  

---

## 0 answers

