2
$\begingroup$

Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ?

Consider for instance the following situation:

two sets, P and NP. In NP, I have the problem A, which can reduce to some unlabeled (forgot to label it) problem, which can, in one branch, reduce to  C, which reduces to D, and then the unlabeled problem reduces through some other branch to Q', which reduces to E and Q. B, another problem proved to be in NP through direct proof, can reduce to Q' as well. Q is then later shown to be in P.

Here, I have my set NP of problems, where problems $A$ and $B$ were proved to be NP-Complete through direct proof, and problems $C$, $D$, $E$, and $Q'$ were proved to be NP-Complete through reduction. I reduce from $Q'$ to $Q$, then later show $Q$ is in $P$. I agree that I then would be able to claim that problems $Q'$ and $B'$ can be claimed to also be in $P$, since we can just reduce them to $Q$. However, why can we make the same claims about $C$, $D$ and $E$ ? there is no (known) way of reducing from them to $Q$, we merely know that they may be "at least as hard" as the unlabeled problem and problem $A$, but can't it be possible that they are harder?

This is why intuitively, it seems to me like we should be showing ways to reduce from all "leaf" problems in NP, to show that $Q$ is also NP-Hard, even if I am told that this is not needed.

$\endgroup$
4
  • 1
    $\begingroup$ can't it be possible that they are harder? No. NP-complete problems are the hardest problems in NP, by definition. Since $Q'$ is NP-complete and (by your assumption) lies in P, we know that any problem from NP ($E$ and $D$ in particular) lies in P. $\endgroup$ – Dmitry Nov 19 '20 at 1:12
  • $\begingroup$ @Dmitry So when we are proving that a problem is NP-Hard (but isn't in NP), is it however correct to say that it is "at least as hard as the hardest problem in NP, but may be even harder" ? – $\endgroup$ – Pierre Duluth Nov 19 '20 at 1:46
  • 1
    $\begingroup$ That's correct. E.g. it's easy to construct an undecidable NP-hard problem. $\endgroup$ – Dmitry Nov 19 '20 at 2:03
  • 1
    $\begingroup$ Every NPC problem (in fact, every NP problem) can be reduced to any NPC problem in poly-time -- that's what NP-completeness means. The direct proofs for $A$ and $B$ must establish this somehow for these problems. So, there should be in-edges to $A$ and $B$ for every other problem in your diagram -- and thus a path of reductions from every problem to $Q$. $\endgroup$ – j_random_hacker Nov 19 '20 at 3:37

Your Answer

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

Browse other questions tagged or ask your own question.