NP Hard problem - explanation from Stephen Boyd

Students used to ask me about this - what is NP-hard problem and why is it important? The exact answer can easily be a topic of a monograph, but I have been looking for a simple yet accurate answer.


Well, NP stands for Non-deterministic Polynomial time. Simply speaking, an NP-complete problem cannot be solved in polynomial time in any known way. NP-Hard/NP-Complete is a way of showing that certain classes of problems are not solvable in realistic time.



Basically, a solution has to be testable in polynomial time. If that's the case, and a known NP problem can be solved using the given problem with modified input (an NP problem can be reduced to the given problem) then the problem is NP complete. NP-complete means the problem is at least as hard as any problem in NP.


On the other hand, there are polynomial-time problems. The class P consists of those problems that are solvable in polynomial time. For example, they could be solved in O(n^k) for some constant k, where n is the size of the input. Simply put, you can write a program that will run in reasonable time.

A decision problem is in P if there is a known polynomial-time algorithm to get that answer. A decision problem is in NP if there is a known polynomial-time algorithm for a non-deterministic machine to get the answer.

There is a good lecture notes about the NP-hard problems [PDF].

A simple and understandable explanation of the NP-hard problem that I like is given by Stephen Boyd:


This explanation is a bit watery, but basically boils down to the following. People identified a bunch of (computationally) very hard problems, to which nobody figured out a polynomial-time algorithm.

When the problem comes in, you measure the size of the data required to describe the problem. Then you look on the number of operations you have to do, and if you can bound that number of computations by polynomial, that's the polynomial-type problem.

There is a catalog of problems that are considered as computationally hard. You can call the problem as NP-hard if it is as hard as any of the problems from that catalog (e.g., travelling salesman).