# NP-Hardness reduction

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.

• 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$. – Igor Shinkar Aug 12 '13 at 9:54
• 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? – Vinicius dos Santos Aug 12 '13 at 17:07
• 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... – Igor Shinkar Aug 13 '13 at 18:41