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?
How is the formal definition of NP-hard equivalent to this colloquial one?
complexity theory;reductions;np hard