0
$\begingroup$

Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP".

It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H".

It doesn't seem obvious to me that those two statements are equivalent. In particular, it's not obvious to me that any problem is always reducible to a "harder" problem.

Why is reducibility an adequate measure of difficulty? To me, the most natural measure of difficulty is worst-case asymptotic complexity. It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

I assume from the definition of NP-hard that this in fact isn't possible. Why not?

Improve this question
$\endgroup$
3
  • $\begingroup$ I encourage you to take a look at our reference question, which explains the connection between those two statements. If that doesn't answer your question, edit your question to explain more clearly what you are confused about. (Note that if we're guaranteed that B is NP-complete, then yes, you can always reduce A to B. If B isn't NP-complete, then there's no reason to think it's at least as hard as the hardest problems in NP. So it's not clear to me what kind of scenario you are worrying about.) $\endgroup$ – D.W.♦ Apr 8 '16 at 5:25
  • $\begingroup$ @D.W. Thanks for the link, but the reference question does not address my question. I've edited the question, hopefully it's now clearer? $\endgroup$ – Ord Apr 8 '16 at 6:19
  • $\begingroup$ @D.W. Re: "If B isn't NP-complete, then there's no reason to think it's at least as hard as the hardest problems in NP." - I guess what I'm confused about is the notion of reducibility as a measure of relative hardness. I understand that if A is reducible to B, then B is at least as hard as A. But if there is no reducibility relationship between A and B, then what? Couldn't there be problems "at least as hard as the hardest problems in NP" when measured via asymptotic lower bounds, but which don't have reducibility relationships to NP-complete problems? $\endgroup$ – Ord Apr 8 '16 at 6:31
2
$\begingroup$

Why is reducibility an adequate measure of difficulty?

It's not; it provides a relative measure of difficulty, relative to the kind of reduction under consideration.

To me, the most natural measure of difficulty is worst-case asymptotic complexity.

That's the idea, but for NP-complete problems in particular we do not know their (worst-case asymptotic time) complexity. By introducing a relative measure of hardness, we can say "A is at least as hard as B" without knowing how hard either of them really is.

having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

That's not the idea behind Karp reductions which we use to define NP-hardness. Read up on the definition.

this complexity is "the worst" possible in NP

There is no such thing as a worst possible complexity; all polynomial complexities are allowed, and there are problems of arbitrary polynomial complexity. You find proofs for this fact in textbooks on the matter.

It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

Keep in mind that complexity classes like P and NP are rough; they ignore polynomial factors. So say we have $\Theta(n^k)$ algorithms for NP-complete $A$ and $B$. We know that $A \leq_p B$ and vice versa, but all that tells us that we can use the algorithm for one to solve the other with polynomial overhead. The degree of this overhead is not specified, and may very well be in $\omega(n^k)$.

Bottom line, you have not yet understood/absorbed the basics and struggle with your faulty intuition contradicting statements you find. I recommend you check out our reference material which covers a wide array of basics and common misconceptions.

Keep in mind that the theory around P and NP defines a measure of hardness. There are certainly others, and some are more appropriate for making some decisions than others.

Improve this answer
$\endgroup$
4
  • $\begingroup$ My understanding of Karp reductions (assuming we're talking about decision problems) is that A can be reduced to B iff there exists a polynomial-time algorithm to transform an arbitrary instance of problem A into an instance of B such that the YES/NO answer to the B problem is the same as the answer to the A problem. Is that not correct? When I said "having an algorithm to solve A is useful for solving B", I was speaking loosely, but I meant that we can perform a polynomial time transformation to a problem in B and then apply the algorithm for A in order to find the solution. $\endgroup$ – Ord Apr 8 '16 at 15:51
  • $\begingroup$ Re: "There is no such thing as a worst possible complexity", right, that's why I put "worst" in quotation marks. I meant an algorithm with a worst-case asymptotic complexity that differs by at most a polynomial factor from an NP-hard problem. $\endgroup$ – Ord Apr 8 '16 at 15:53
  • $\begingroup$ "Keep in mind that the theory around P and NP defines a measure of hardness. There are certainly others, and some are more appropriate for making some decisions than others." -> okay, so is it accurate to say that there can in fact exist problems A and B with the properties I specified in my question? $\endgroup$ – Ord Apr 8 '16 at 15:55
  • $\begingroup$ @Ord Not in the way you specified, no. But apparently you did not write what you had in mind. $\endgroup$ – Raphael♦ Apr 9 '16 at 9:09

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.