- NP Hard
- Non-deterministic polynomial, a type of computability problem; see Complexity theory, Complexity classes P and NP, NP-Complete.
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).