<p>To expand on Bruno and Emil's comments, the Berman-Hartmanis isomorphism theorem [1, p.312] says yes, provided <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are <em>paddable</em>:</p>
<blockquote>
<p>If both <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are paddable, there exists a polynomial-time isomorphism <span class="math-container">$\psi$</span> from strings over the alphabet of <span class="math-container">$A$</span> to strings over the alphabet of <span class="math-container">$B$</span>, that is, a bijection such that <span class="math-container">$x\in A$</span> iff <span class="math-container">$\psi(x) \in B$</span>, where <span class="math-container">$\psi$</span> and its inverse are computable in polynomial time.</p>
</blockquote>
<p>Formally, a language <span class="math-container">$L$</span> is <em>paddable</em> if there are polynomial-time computable functions pad<span class="math-container">$(x, p)$</span> and extractPad<span class="math-container">$(x)$</span> such that, for all strings <span class="math-container">$x$</span> and <span class="math-container">$p$</span></p>
<ol>
<li>pad<span class="math-container">$(x, p) \in L$</span> iff <span class="math-container">$x \in L$</span>, and</li>
<li><span class="math-container">$p ={} $</span> extractPad<span class="math-container">$($</span>pad<span class="math-container">$(x, p))$</span>.</li>
</ol>
<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).</p>
<hr />
<p>Per Wikipedia, there is some reasonable evidence <a href="https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture#Evidence" rel="nofollow noreferrer">against</a> this conjecture.</p>
<hr />
<p>[1] <em>Berman, L.; Hartmanis, J.</em>, <a href="https://doi.org/10.1137/0206023" rel="nofollow noreferrer"><strong>On isomorphisms and density of NP and other complete sets</strong></a>, SIAM J. Comput. 6, 305-322 (1977). <a href="https://zbmath.org/?q=an:0356.68059" rel="nofollow noreferrer">ZBL0356.68059</a>.</p>

CC BY-SA 4.0
2024-04-06T13:29:44.637Z
2024-04-10T14:02:28.993Z
2024-04-10T14:02:28.993Z
Neal Young
<p>If $A$ and $B$ are NP-complete problems, is there a <em>bijective</em> function $f$ (computable in polynomial time) such that $w\in A$ iff $f(w)\in B$?</p>

CC BY-SA 3.0
2014-12-19T15:06:27.027Z
I am not the author of the downvote, but the answer to your question is not known and is called the [Berman-Hartmanis conjecture](http://en.wikipedia.org/wiki/Berman–Hartmanis_conjecture).
Bruno
CC BY-SA 3.0
2014-12-19T16:52:28.307Z
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
CC BY-SA 3.0
2014-12-19T20:53:56.103Z
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
CC BY-SA 3.0
2014-12-20T04:55:21.890Z
@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
CC BY-SA 3.0
2014-12-21T05:16:26.610Z
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.
Tsuyoshi Ito
CC BY-SA 4.0
2024-04-06T22:42:43.987Z
Related: https://cs.stackexchange.com/q/91219/4678
Neal Young
<cc.complexity-theory><np-complete>
Bijection between NP-complete problems
j8723
# Bijection between NP-complete problems

(Asked by: username_0 on 2014-12-19)

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

**Tags:** cc.complexity-theory, np-complete
> **Comments:**
> **username_1**: I am not the author of the downvote, but the answer to your question is not known and is called the [Berman-Hartmanis conjecture](http://en.wikipedia.org/wiki/Berman–Hartmanis_conjecture).  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: @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).  
> **username_5**: 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.  
> **username_6**: Related: https://cs.stackexchange.com/q/91219/4678  

---

## 1 answers

### Answer by username_6 on 2024-04-06. Score: 5

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](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture#Evidence) this conjecture.

---

[1] *Berman, L.; Hartmanis, J.*, [**On isomorphisms and density of NP and other complete sets**](https://doi.org/10.1137/0206023), SIAM J. Comput. 6, 305-322 (1977). [ZBL0356.68059](https://zbmath.org/?q=an:0356.68059).


---

