CentralNotice NP-hard From Wikipedia, the free encyclopedia Jump to: navigation , search For a gentler introduction, see P versus NP problem . Euler diagram for P , NP , NP-complete , and NP-hard set of problems NP-hard ( N on-deterministic P olynomial-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 . [ 1 ] :80 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 as hard. [ 2 ] A common mistake is to think that the NP in NP-hard stands for non-polynomial . Although it is widely suspected that there are no polynomial-time algorithms ...