# 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$?

• why the downvote? – j8723 Dec 19 '14 at 14:12
• I am not the author of the downvote, but the answer to your question is not known and is called the Berman-Hartmanis conjecture. – Bruno Dec 19 '14 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. – Emil Jeřábek Dec 19 '14 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. – Lopsy Dec 19 '14 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). – Joshua Grochow Dec 20 '14 at 4:55