NP-Hard

NP Hard

Non-deterministic polynomial, a type of computability? problem; see Complexity theory

Note that the N in NP does not stand for 'non'; it is not yet proved that NP != P (though we suspect it quite strongly!)
An NP-Hard problem is one which, if a polynomial solution existed for it, then all problems in NP would have a polynomial solution (ie NP=P) The preceding sentence sounds somewhat like a tautology?. It just says that NP-Hard problems have a common property .

An example of an NP-Hard problem is the travelling salesman problem (TSP).