Karp (many-one) reducibility between $NP$-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. Berman-Hartmanis isomorphism conjecture states that between any pair of $NP$-complete problems there is bijection $f$ which is computable and invertible in polynomial-time.

I am interested in polynomial-time invertability of Karp reductions between *natural* NP-complete problems. Every Karp reduction $f$ is polynomial-time computable but it is not clear whether $f^{-1}$ is also computable in polynomial-time.

I am looking for Karp reduction $f$ between two *natural* NP-complete problems where its inverse $f^{-1}$ is **not known** to be polynomial-time computable.

Is there a pair of natural NP-complete problems A, B and polynomial-time computable injective reduction $f$ from A to B (where $f^{-1}$ is not know to be computable in polynomial-time)?

P.S. Natural problem means that the problem is not an artificially made up problem to answer the question (or similar ones) and people are interested in the problem independently (defined by Kaveh).

existsa non-invertible reduction between them (which is easy enough to construct, for typical NP-complete problems), or whetherallreductions between the two problems are non-invertible (which contradicts the Berman-Hartmanis conjecture)? $\endgroup$ – Emil Jeřábek supports Monica May 11 '18 at 8:21