0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – NL1992
    Commented Feb 10, 2023 at 20:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Feb 11, 2023 at 7:20

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.