What are the differences between NP, NP-Complete a

Question

What are the differences between NP, NP-Complete and NP-Hard?

I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different then what's out there, or it's out there and I'm not aware.

Answer 1

There are really nice answers for this particular question, so there is no point to write my own explanation. So I will try to contribute with an excellent resource about different classes of computational complexity.

For someone who thinks that computational complexity is only about P and NP, here is the most exhaustive resource about different computational complexity problems. Apart from problems asked by OP, it listed approximately 500 different classes of computational problems with nice descriptions and also the list of fundamental research papers which describe the class.

Answer 2

P (Polynomial Time) : As name itself suggests, these are the problems which can be solved in polynomial time.

NP (Non-deterministic-polynomial Time) : These are the decision problems which can be verified in polynomial time. That means, if I claim that there is a polynomial time solution for a particular problem, you ask me to prove it. Then, I will give you a proof which you can easily verify in polynomial time. These kind of problems are called NP problems. Note that, here we are not talking about whether there is a polynomial time solution for this problem or not. But we are talking about verifying the solution to a given problem in polynomial time.

NP-Hard : These are at least as hard as the hardest problems in NP. If we can solve these problems in polynomial time, we can solve any NP problem that can possibly exist. Note that these problems are not necessarily NP problems. That means, we may/may-not verify the solution to these problems in polynomial time.

NP-Complete : These are the problems which are both NP and NP-Hard. That means, if we can solve these problems, we can solve any other NP problem and the solutions to these problems can be verified in polynomial time.

Answer 3

NP-complete problems are those problems that are both NP-Hard and in the complexity class NP. Therefore, to show that any given problem is NP-complete, you need to show that the problem is both in NP and that it is NP-hard.

Problems that are in the NP complexity class can be solved non-deterministically in polynomial time and a possible solution (i.e., a certificate) for a problem in NP can be verified for correctness in polynomial time.

An example of a non-deterministic solution to the k-clique problem would be something like:

1) randomly select k nodes from a graph

2) verify that these k nodes form a clique.

The above strategy is polynomial in the size of the input graph and therefore the k-clique problem is in NP.

Note that all problems deterministically solvable in polynomial time are also in NP.

Showing that a problem is NP-hard typically involves a reduction from some other NP-hard problem to your problem using a polynomial time mapping: http://en.wikipedia.org/wiki/Reduction_(complexity)

Answer 4

The easiest way to explain P v. NP and such without getting into technicalities is to compare "word problems" with "multiple choice problems".

When you are trying to solve a "word problem" you have to find the solution from scratch. When you are trying to solve a "multiple choice problems" you have a choice: either solve it as you would a "word problem", or try to plug in each of the answers given to you, and pick the candidate answer that fits.

It often happens that a "multiple choice problem" is much easier than the corresponding "word problem": substituting the candidate answers and checking whether they fit may require significantly less effort than finding the right answer from scratch.

Now, if we would agree the effort that takes polynomial time "easy" then the class P would consist of "easy word problems", and the class NP would consist of "easy multiple choice problems".

The essence of P v. NP is the question: "Are there any easy multiple choice problems that are not easy as word problems"? That is, are there problems for which it's easy to verify the validity of a given answer but finding that answer from scratch is difficult?

Now that we understand intuitively what NP is, we have to challenge our intuition. It turns out that there are "multiple choice problems" that, in some sense, are hardest of them all: if one would find a solution to one of those "hardest of them all" problems one would be able to find a solution to ALL NP problems! When Cook discovered this 40 years ago it came as a complete surprise. These "hardest of them all" problems are known as NP-hard. If you find a "word problem solution" to one of them you would automatically find a "word problem solution" to each and every "easy multiple choice problem"!

Finally, NP-complete problems are those that are simultaneously NP and NP-hard. Following our analogy, they are simultaneously "easy as multiple choice problems" and "the hardest of them all as word problems".