NP-Hard

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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).