2
$\begingroup$

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

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

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.