6
$\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$
6
  • 7
    $\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
    Commented Dec 19, 2014 at 15:06
  • 7
    $\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$ Commented Dec 19, 2014 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
    Commented Dec 19, 2014 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$ Commented Dec 20, 2014 at 4:55
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 21, 2014 at 5:16

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.