I have a problem $\Pi_1$ that I want to show that is NP-hard. I know that I must find an NP-hard problem $\Pi_2$ and a polynomial time reduction $f()$ from instances of $\Pi_2$ to $\Pi_1$ such that $I_2$ is an Yes-instance of $\Pi_2$ iff $I_1=f(I_2)$ is an Yes-instance of $\Pi_1$.

What if I find a (constant sized) family of reductions $f_i()$ such that $I_2$ is an Yes-instance of $\Pi_2$ iff at least one $f_i(I_2)$ is an Yes-instance of $\Pi_1$? Is this enough? Is there a way of translating this one in the "classical" definition? How to formalize this?

I know that in the second situation I can say that I can't solve $\Pi_1$ in polynomial time unless P=NP, but I'm no sure that is equivalent of saying that $\Pi_1$ is NP-hard.

  • $\begingroup$ Here is a way to translate this into a "classical" definition of reduction, that is Karp-reduction. Suppose you have $k$ reductions $f_1,\dots,f_k$. You can define a language $\Pi_2^k = \{x_1,\dots,x_k : \exists i. x_i \in \Pi_2\}$. Then (1) The problem $\Pi_2^k$ is NP-complete. (2) The reduction $F(x) = (f_1(x),\dots,f_k(x))$ is a Karp reduction from $\Pi_1$ to $\Pi_2^k$. $\endgroup$ – Igor Shinkar Aug 12 '13 at 9:54
  • $\begingroup$ I'm not sure I really got your idea. You defined a new problem $\Pi_2^k$, which can be shown NP-complete (from a reduction from $\Pi_2$, right? But how does the reduction in (2), from $\Pi_1$ to $\Pi_2^k$, help? I think I would need a reduction in the opposite direction, right? $\endgroup$ – Vinicius dos Santos Aug 12 '13 at 17:07
  • 1
    $\begingroup$ You are right, i got confused... What I wrote shows a reduction $\Pi_2 \leq_p \Pi_1^k$,which implies that $\Pi_1^k$ is NP-hard. I don't see how to prove $\Pi_1^k \leq_p \Pi_1$. My guess is that there should be such a reduction since "morally" these problems look equivalent, but i could be wrong... $\endgroup$ – Igor Shinkar Aug 13 '13 at 18:41

NP-hardness is usually defined using many-to-one reductions, for various reasons, for example to separate NP from coNP (there was some question about it either here or in cstheory). What you're describing is a specific case of more general Turing reductions, which is more common in classical recursion theory, and it is natural since it has the consequences you mention. Unfortunately, the definition of NP-hardness requires a many-to-one reduction.

| cite | improve this answer | |
  • $\begingroup$ Did you mean that one? I think this question is a duplicate; do you disagree? $\endgroup$ – Raphael Aug 11 '13 at 13:22
  • $\begingroup$ Right, this question is a duplicate and should be closed. Thanks for finding the older question! $\endgroup$ – Yuval Filmus Aug 11 '13 at 15:08
  • 1
    $\begingroup$ I don't see how this question is a duplicate. See my comment inside the question $\endgroup$ – Igor Shinkar Aug 12 '13 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.