What does NP-hard mean? A lot of times you can solve a problem by reducing it to a different problem. I can reduce Problem B to Problem A if, given a solution to Problem A, I can easily construct a solution to Problem B. (In this case, “easily” means “in polynomial time.”)
If a problem is NP-hard, this means I can reduce any problem in NP to that problem. This means if I can solve that problem, I can easily solve any problem in NP. If we could solve an NP-hard problem in polynomial time, this would prove P = NP.
NP-complete
A problem is NP-complete if the problem is both
- NP-hard, and
- in NP.
Example 1: Let us consider the classical version of TSP (Travelling Sales Person) problem – find the shortest distance between two cities on a map such that the sales person visits each city only once. This is a constrained optimization problem. To solve this one needs to solve for Hamiltonian Cycles first. In 1972, Prof. Richard Karp proved that Hamiltonian cycles are NP-complete. Now, the classical TSP is at least as hard as a NP-complete problem. Prof. Karp thus proved the NP-hardness of the classical TSP. So classical TSP is a NP-hard problem. Note that it is not *strictly* NP-hard.
(There is a decision version of this problem – given distance L between two cities, can you give a better l < L ? This requires a yes/no answer. This decision version of classical TSP is NP-complete and not NP-hard.)
Example 2: The halting problem is NP-hard. Given an input, will the Turing machine halt? A Turing machine can be given a constraint to halt – when it solves the SAT problem it can halt. The solution to SAT can be verified in PTIME and hence once the machine outputs the correct solution it halts. However, SAT is a NP-complete problem. So the *general* halting problem should be at least as hard as the SAT problem. Hence it is a NP-hard problem.
