# Bijection between NP-complete problems

If $A$ and $B$ are NP-complete problems, is there a bijective function $f$ (computable in polynomial time) such that $w\in A$ iff $f(w)\in B$?

• I am not the author of the downvote, but the answer to your question is not known and is called the Berman-Hartmanis conjecture. Commented Dec 19, 2014 at 15:06
• Actually, the Berman–Hartmanis conjecture is stronger: it also requires the inverse of $f$ to be polynomial-time. Nevertheless, I’d be surprised if the answer is known even to the weaker form of question. Commented Dec 19, 2014 at 16:52
• Suppose sparse NP-complete languages exist (i.e. only polynomially many yes instances per input size). Then you could set $B$ to a sparse language, $A$ to a non-sparse language, and no function $f$ would exist. It is wide open (and stronger than P $\neq$ NP) whether sparse NP-complete languages exist. Commented Dec 19, 2014 at 20:53
• @Lopsy: If a sparse $\mathsf{NP}$-complete language exists, then $\mathsf{P} = \mathsf{NP}$... Exactly the line of reasoning you use is one of the major motivations for looking at sparsity in the first place (going back to Berman-Hartmanis). Commented Dec 20, 2014 at 4:55
• In light of Emil Jeřábek’s comment, I am more interested in whether this statement is equivalent to the Berman–Hartmanis conjecture or there is some evidence that this statement is strictly weaker. Commented Dec 21, 2014 at 5:16

To expand on Bruno and Emil's comments, the Berman-Hartmanis isomorphism theorem [1, p.312] says yes, provided $$A$$ and $$B$$ are paddable:

If both $$A$$ and $$B$$ are paddable, there exists a polynomial-time isomorphism $$\psi$$ from strings over the alphabet of $$A$$ to strings over the alphabet of $$B$$, that is, a bijection such that $$x\in A$$ iff $$\psi(x) \in B$$, where $$\psi$$ and its inverse are computable in polynomial time.

Formally, a language $$L$$ is paddable if there are polynomial-time computable functions pad$$(x, p)$$ and extractPad$$(x)$$ such that, for all strings $$x$$ and $$p$$

1. pad$$(x, p) \in L$$ iff $$x \in L$$, and
2. $$p ={}$$ extractPad$$($$pad$$(x, p))$$.

According to Wikipedia, Berman and Hartmanis conjectured that all NP-complete problems are paddable. Furthermore this conjecture is equivalent to the conjecture that all pairs of NP-complete languages admit poly-time invertible reductions (which is slightly stronger than OP's question).

Per Wikipedia, there is some reasonable evidence against this conjecture.

[1] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. Comput. 6, 305-322 (1977). ZBL0356.68059.