1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ If I fix two NP-complete problems, are you asking whether there exists a non-invertible reduction between them (which is easy enough to construct, for typical NP-complete problems), or whether all reductions between the two problems are non-invertible (which contradicts the Berman-Hartmanis conjecture)? $\endgroup$
    – Emil Jeřábek
    Commented May 11, 2018 at 8:21
  • $\begingroup$ Also, what exactly do you mean by "the inverse"? Reductions are in general neither injective nor surjective, so they don't have an actual inverse at all, never mind polynomial time. $\endgroup$
    – Emil Jeřábek
    Commented May 11, 2018 at 8:24
  • $\begingroup$ @EmilJeřábek Berman-Hartmanis conjecture states that between any pair of natural NP-complete problems there is bijection $f$ which is computable and invertible in polynomial-time. My question, 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)? $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 11, 2018 at 12:46
  • $\begingroup$ @EmilJeřábek All known Karp reductions between natural NP-complete problems are injective (one-one) functions or can be made injective (I read this in some reference. I'll post it ASAP). $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 11, 2018 at 12:58
  • $\begingroup$ There are easily described non-injective Karp reductions between some natural NP-complete problems, so it would be interesting to know what "can be made injective" means. $\endgroup$
    – Andreas Blass
    Commented May 11, 2018 at 13:45

1 Answer 1

Reset to default
1
$\begingroup$

Such a non-invertible reduction exists between any pair of “natural” NP-complete problems (and conjecturally, between any pair of NP-complete problems), as long as non-invertible poly-time functions exist at all.

While the Berman–Hartmanis conjecture in general is open, various particular cases of it hold unconditionally. In particular, “natural” NP-complete problems are known to satisfy the conjecture. So, let me simply define for the sake of this post that an NP-complete language is natural if it is poly-time isomorphic to SAT.

This means all natural NP-complete languages are paddable, and in particular, any such language $A$ is poly-time isomorphic to the language $A\oplus\emptyset=\{0_\smile x:x\in A\}$. Now, if $A$ and $B$ are two such languages, let $f$ be any reduction of $A$ to $B$ (which may be asumed to be a poly-time isomorphism if desired), and let $g\colon\{0,1\}^*\to\{0,1\}^*$ be an arbitrary poly-time function. Then the function $f\oplus g$ defined by $$\begin{align} (f\oplus g)(0_\smile x)&=0_\smile f(x),\\ (f\oplus g)(1_\smile x)&=1_\smile g(x), \end{align}$$ is a reduction of $A\oplus\emptyset$ to $B\oplus\emptyset$, which retains all bad properties of $g$; so, if we chose $g$ not poly-time invertible, then $f\oplus g$ is not poly-time invertible either. We can construct a reduction of $A$ to $B$ with the same properties by composing with the poly-time isomorphisms $A\simeq_p A\oplus\emptyset$ and $B\oplus\emptyset\simeq_p B$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I am looking for concrete example. Yours is not since function $g$ is unspecified. Besides the reduction is artificial since its not of the flavor we encounter between natural NP-complete problems. $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 11, 2018 at 20:06
  • 1
    $\begingroup$ Then fix $g$ as your favourite specific example. $\endgroup$
    – Emil Jeřábek
    Commented May 11, 2018 at 20:18
  • $\begingroup$ I guess you are suggesting that g is a candidate one-way function. In that case, your reduction is artificial since we do not encounter such reduction between natural NP-complete problems. $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 11, 2018 at 20:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .