Invertability of Karp reductions

Question

Karp 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$.

I am interested in polynomial-time invertability of Karp reductions between natural NP-complete problems.

Is it true that every Karp reduction $f$ is also polynomial-time invertible (i.e. $f^{-1}$ is polynomial-time computable)?

To clarify, Is there a Karp reduction $f$ between two natural NP-complete problems where its inverse $f^{-1}$ is not known to be polynomial-time computable?

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).

P.S. It is known that all known Karp reductions between natural NP-complete problems are injective (or can easily made injective).

Answer 1

1. YES if $\mathrm{P}\neq \mathrm{NP}$ and the $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones). In short, this is the equivalent statement of your conjecture.

Unconditionally, every $\mathrm{NP}$ problem not necessarily complete can be reduced to $3$-$\mathrm{SAT}$ by a reduction $f$ which is poly-time invertible. And composition $f \circ g$ of efficiently invertible $f$ and $g$ is also efficiently invertible. Therefore, if somehow we prove that $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones), then your conjecture holds.

When reducing to $3$-$\mathrm{SAT}$, simply append dummy clauses to the $3$-$\mathrm{SAT}$ instance. These dummy clauses just encodes the original instance. And of course, these are trivially satisfiable with brand-new dummy variables.

For example: suppose $x=x_1x_2\dots x_n$ is the original instance and your $3$-$\mathrm{SAT}$ instance already has $k$ variables, do the following:

for each original bit $x_i$:

• if $x_i=0$, add dummy clause $x_{k+1}\lor \lnot x_{k+1}$ if $k+1$ is even, otherwise add dummy clause $x_{k+2}\lor \lnot x_{k+2}$
• if $x_i=1$, add dummy clause $x_{k+1}\lor \lnot x_{k+1}$ if $k+1$ is odd, otherwise add dummy clause $x_{k+2}\lor \lnot x_{k+2}$

• $k$ := $k + 1$

  2. NO if $\mathrm{P} = \mathrm{NP}$. This is because if so, a sparse language can be $\mathrm{NP}$-complete rendering hopeless a poly-time injective reduction (from a non-spare language to it).

  3. Your conjecture is impied by the much stronger isomorphism conjecture. That is why many attempts to partially resolve that conjecture (e.g. by deduce it from weaker statements like yours) all fail up to now.