5
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Aug 12, 2013 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
    Commented Aug 12, 2013 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
    Commented Aug 13, 2013 at 18:41

1 Answer 1

Reset to default
6
$\begingroup$

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.

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

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.