computer science//complexity theory//NP-hardness

NP-hardness is the property of a problem being at least as hard as every problem in NP, the class whose solutions can be checked quickly, so that no algorithm is known that guarantees the optimum in a time growing only polynomially with the size of the input in the worst case. For an engineer it is a warning label on a planning, scheduling or allocation problem: exact answers will get expensive fast as the instance grows, and the design has to choose what to give up. An NP-hard problem that is also in NP, typically the yes-or-no version of an optimization, is **NP-complete**.

NP-hardness is the property of a problem being at least as hard as every problem in NP, the class whose solutions can be checked quickly, so that no algorithm is known that guarantees the optimum in a time growing only polynomially with the size of the input in the worst case. For an engineer it is a warning label on a planning, scheduling or allocation problem: exact answers will get expensive fast as the instance grows, and the design has to choose what to give up. An NP-hard problem that is also in NP, typically the yes-or-no version of an optimization, is NP-complete.

The label is easy to misread in both directions. A huge search space does not make a problem hard: matching 20 robots to 20 orders has 20!≈2.4⋅101820!\approx 2.4\cdot10^{18}20!≈2.4⋅1018 possible pairings, yet the assignment problem is solved exactly in O(n3)O(n^3)O(n3) because its structure lets an algorithm avoid enumerating them. Change one thing, allow several drones to go to the same fire with diminishing returns, and the problem becomes weapon-target assignment, whose decision version was proved NP-complete in 1986.

NP-hard means choosing between exactness, size and time.

The label is often read as impossible, and it is far from that: with tens of agents, branch and bound or an integer linear programming solver usually returns the optimum in seconds or minutes; for hundreds of agents in real time, a heuristic with a local search on top gives a good answer within the period.

The classification is about the worst case. Commercial solvers find optimal schedules for many industrial instances far larger than the theory would suggest, because real instances rarely look like the adversarial ones; the risk is the occasional instance that does, which is why a time limit and a fallback answer belong in any loop that calls an exact solver.

It is one rung of a ladder in complexity theory. Some decision problems are harder still: solving a finite-horizon POMDP exactly is PSPACE-complete, which is why partially observed decisions are solved approximately in practice.