NP-hardness
/ en-pee hard /
Some problems are 'at least as hard as the hardest problems in NP', so hard that a fast algorithm for any one of them would unlock fast algorithms for thousands of others. We call such a problem NP-hard. The intuition: it is a universal bottleneck — every problem in NP can be re-expressed as a special case of it, so cracking it cracks them all. Being NP-hard is a strong statement of difficulty, and (assuming the widely believed P is not NP) a near-guarantee that no polynomial-time algorithm exists.
Precisely, a problem H is NP-hard if EVERY problem A in NP reduces to H by a polynomial-time reduction: A <=p H for all A in NP. Because <=p preserves and chains, this single condition means a polynomial-time algorithm for H would give a polynomial-time algorithm for every problem in NP (translate then solve), collapsing P and NP into one. In practice you almost never check 'all A in NP' directly. Instead you use transitivity: once you know one problem (say SAT, by Cook-Levin) is NP-hard, you prove a new problem H is NP-hard by reducing SAT (or any known NP-hard problem) TO H. Since everything in NP already reduces to SAT, and SAT <=p H, everything in NP reduces to H — done. The direction is the whole game: reduce a KNOWN-hard problem into your target.
Two honest points. First, NP-hard does NOT require the problem to be in NP. The halting problem and the optimisation version of TSP ('find the shortest tour', not 'is there a tour of length <= B?') are NP-hard but not in NP — they can be even harder, undecidable in the halting case. A problem that is BOTH NP-hard AND in NP is the special, central case called NP-complete. Second, NP-hard is not a PROOF of exponential difficulty: P-versus-NP is open, so 'NP-hard' formally means 'no polynomial algorithm unless P = NP', not 'provably needs exponential time'. In practice, though, it is the standard, well-founded reason to stop hunting for an exact fast algorithm and start coping — approximate, restrict the inputs, or accept exponential time on small cases.
To show vertex cover is NP-hard, you do NOT enumerate all of NP. You reduce a single known-hard problem, 3-SAT, to it: given a 3-SAT formula, you build a graph and a number k such that the graph has a vertex cover of size k exactly when the formula is satisfiable. Since 3-SAT is NP-hard and 3-SAT <=p vertex-cover, vertex cover inherits NP-hardness by transitivity.
Prove NP-hardness by reducing a known NP-hard problem INTO yours — never the reverse.
NP-hard does not mean 'in NP', and it does not prove exponential time (P-vs-NP is open). It means 'as hard as anything in NP'. The fatal direction error: reducing your problem TO a known-hard one shows nothing — you must reduce the known-hard one to yours.