2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ "Natural" seems vague and ill-defined. Are problems allowed to be about cryptography? to refer to a one-way function? Or would you consider those unnatural? $\endgroup$
    – D.W.
    Apr 29, 2018 at 5:57
  • $\begingroup$ @D.W. Natural 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 (as defined by Kaveh). $\endgroup$ Apr 29, 2018 at 7:34
  • $\begingroup$ @D.W. Combinatorial worst-case one-way functions would be very interesting (between a pair of two natural NP-complete problems). $\endgroup$ Apr 29, 2018 at 8:09
  • $\begingroup$ Related: cstheory.stackexchange.com/q/27896/8237 $\endgroup$
    – Neal Young
    Apr 6 at 22:43

2 Answers 2

2
$\begingroup$

The Berman-Hartmanis isomorphism theorem [1, p.312] says that poly-time invertible reductions exist between any two paddable NP-complete languages:

If two NP-complete languages $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))$.

I believe Berman and Hartmanis conjectured that all NP-complete languages are paddable. I think no counter-example is known, although Wikipedia states that there is some plausible evidence against this conjecture.

This doesn't quite answer the question, even for paddable languages, because it doesn't say that every poly-time reduction is invertible. And indeed not all reductions are invertible (i.e., injective), much less poly-time invertible. I'm not sure what OP means exactly by "P.S. It is known that all known Karp reductions between natural NP-complete problems are injective (or can easily made injective)." But perhaps OP intends to allow some kind of modification to the reduction.

[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$
0
$\begingroup$
  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$

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

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

$\endgroup$
1
  • $\begingroup$ I think you are showing that 3-SAT is paddable. $\endgroup$
    – Neal Young
    Apr 6 at 22:51

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.