# Polynomially many instances imply a polynomial reduction?

I have a language $$L$$ which is NP-hard and I have another language $$L_1$$, s.t. if I take an instance $$q$$ of the decision problem corresponding to $$L$$, and if one of polynomially many instances, $$f_1(q),\ldots,f_{p(|q|)}(q)$$ is in $$L_1$$, then $$q\in L$$.

Is this enough to say that $$L_1$$ is NP-hard?

Do you have a polynomial-time algorithm to construct those polynomially instances? If you can construct those polynomially many instances in polynomial time, then you have a Cook reduction (also known as a polynomial-time Turing reduction), not a many-one reduction. So your question then becomes: if we have a Cook reduction from $$L$$ to $$L_1$$, and if $$L$$ is NP-hard, then does it follow that $$L_1$$ is NP-hard?

The answer depends on the definition of NP-hard that you use, which is a little tricky, so let me start with a simpler question:

If we have a Cook reduction from $$L$$ to $$L_1$$, and if $$L$$ is NP-complete, then does it follow that $$L_1$$ is NP-complete? Answer: No. But it is strong evidence, if it is also known that $$L_1$$ is in NP. NP-completeness is defined in terms of many-one reductions, not Cook reductions. The existence of a Cook reduction is not currently known to imply the existence of a many-one reduction (it is a famous open problem, and it might be true - we don't know of any counterexamples - but we don't have a proof of such an implication). See Graph problem known to be $NP$-complete only under Cook reduction, Can we construct a Karp reduction from a Cook reduction between NP problems?.

Back to the question about NP-hardness. That is harder to answer, because there is not universal agreement about what precisely NP-hard means. There are multiple reasonable ways to define NP-hard. One definition is in terms of many-one reductions ($$H$$ is NP-hard if for every $$G$$ in NP, there is a many-one reduction from $$G$$ to $$H$$), and another definition is in terms of Cook reductions ($$H$$ is NP-hard if for every $$G$$ in NP, there is a Cook reduction from $$G$$ to $$H$$). The answer to the question is "no" for the first, "yes" for the second.

In particular, if we have a Cook reduction from $$L$$ to $$L_1$$, and if $$L$$ is NP-hard under Cook reductions, then it does follow that $$L_1$$ is NP-hard under Cook reductions. If we have a Cook reduction from $$L$$ to $$L_1$$, and if $$L$$ is NP-hard under many-one reductions, then it is not known whether this implies $$L_1$$ is NP-hard under many-one reductions (in particular consider $$L$$ to be SAT and $$L_1$$ to be the complement of SAT; then if NP $$\ne$$ co-NP, as is widely conjectured, then $$L$$ is NP-hard under many-one reductions but the complement of SAT is not NP-hard under many-one reductions). See also If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?.

Finally, if you don't have a polynomial-time algorithm to construct those polynomially instances, then you cannot conclude anything at all. For instance, consider the case where $$L_1$$ is a language in P, and $$L$$ is 3SAT; if you have exponential time, you can determine whether $$q$$ is in $$L$$, and then let $$f_1(q)$$ be a member of $$L_1$$ if $$q$$ is in $$L$$ or a non-member of $$L_1$$ if $$q$$ is not in $$L$$.

• Thank you for the elaborate explanation. Each of my polynomially many instances can be constructed polynomially. It seems like I do have a Cook reduction in my case, and the language is in NP. If I understood the other sources you linked to correctly, I cannot conclude that this is NPC unless I have some special properties of the language I’m dealing with? Also, if this problem is in P, it still proves that P=NP. So perhaps at least that is something useful I can say. Feb 10, 2023 at 20:17
• @NL1992, yes, that sounds right to me. As a heuristic, if you have found a Cook reduction, then my guess is that with more work it will likely be possible to find a many-one reduction.
– D.W.
Feb 11, 2023 at 7:20