I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).

Let's assume that you have proven that a problem Y is NP-Hard, and you have a problem X which you know is in NP, and you would like to solve.

To solve X, which of the following reductions would be carried out?

  1. X -> Y
  2. Y -> X

Which of the following? i.e. would you reduce X to Y or vice-versa, if you would like to solve X which is in NP, and Y which is NP-Hard?

  • 1
    $\begingroup$ Please don't crosspost. $\endgroup$ – Raphael Jun 11 '12 at 1:16
  • $\begingroup$ Why isn't the correct answer obviously "Neither"? $\endgroup$ – JeffE Jun 13 '12 at 5:12

What do you mean by "solve"?

  1. Do you want to provide an algorithm for the problem? Then you reduce $X$ to $Y$ and use a supposedly known algorithm $A_Y$ to solve it. That is, if you have an instance $x$ of $X$ , you use the reduction $f$ to convert it to some instance $y=f(x)$ of $Y$ and then use the algorithm that solves $Y$ on instance $y$. In that way, you have an algorithm with running time $T_f + T_{A_Y}$ for $X$.

  2. What if by solve you mean to find out the complexity of $X$, in this case prove that $X$ is $\mathbb{NP}$-hard?

Instead of providing a one-time answer, I would like to show you why this answer holds. As it is common in mathematics and science in general, the level of abstraction you are working on might be helpful, yet it covers some fine details. For example, the intuitive measurement of the resources spent, most notably time, has its basis on a complicated scheme with the purpose to define reductions with some desirable properties.

For polynomial-time reductions, like the ones we use to prove $\mathbb{NP}$-completeness, you can treat reductions as the $\leq$ operator (in mathematical terms, polynomial-time reductions define a partial order. In general, reductions define a preorder). That is, the right hand side is always at least as hard as the left hand. At this point of the discussion, I beg you to remember that we compare problems, so in the extreme case that a single instance is hard and the rest easy, this single instance determines the complexity of the entire problem.

Now, we can answer your question. We know that $Y$ is a $\mathbb{NP}$-hard problem and we want to prove that $X$ is at least as hard as $Y$. Therefore, thinking in terms of the $\leq$ operator, it is suffices to reduce $Y$ to $X$, that is $Y \leq _{p} X$. Provided you have that reduction, $X$ is at least as hard as $Y$. And $Y$ is $\mathbb{NP}$-hard, so $X$ must be $\mathbb{NP}$-hard too. By definition, if you can prove that $X \in \mathbb{NP}$, then $X$ is $\mathbb{NP}$-complete.

At the end of this discussion, you might have noticed a problem. The satisfiability problem $SAT$ is $\mathbb{NP}$-complete, yet there exists a simple $O(n)$ nondeterministic time algorithm for it. How can it be as least as hard as any problem in $\mathbb{NP}$? The answer is simple: Polynomial-time differences are not of an interest to us, as we have defined our model. So, the polynomial-time reduction behaves like the $\leq$ operator, though it allows the complexity of the left hand side to be larger up to a polynomial than the running time of the harder problem. This is why we don't use exponential time reductions, since the error margin would be larger than the complexity of the problems themselves (and the definition of the respective classes), making them useless.

| cite | improve this answer | |
  • 3
    $\begingroup$ In general, there is no such thing as "a single instance that is hard". $\endgroup$ – JeffE Jun 10 '12 at 10:11
  • $\begingroup$ Yes, especially on "natural" problems. I suppose such an extremity wouldn't be of interest, but I meant it as a principle rather than an example. I'll change the wording to reflect that. $\endgroup$ – chazisop Jun 10 '12 at 12:43
  • $\begingroup$ JeffE’s point is not naturalness. Your wording “a single instance is hard and the rest easy” is undefined, because complexity is a notion defined on problems, not on instances. $\endgroup$ – Tsuyoshi Ito Jun 10 '12 at 14:38
  • 2
    $\begingroup$ More importantly, for any particular instance, there is an algorithm that is efficient for that particular instance. (If the input is instance X, output the correct answer for instance X; otherwise, use brute force.) $\endgroup$ – JeffE Jun 10 '12 at 16:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.