NP-hardness (
non-deterministic polynomial-time hard), in
computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in
NP". More precisely, a problem
H is NP-hard when every problem
L in NP can be
reduced in
polynomial time to
H. As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard.