NP vs NP-Complete vs NP-Hard

Question

What are the differences between NP vs NP-Complete vs 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

http://en.wikipedia.org/wiki/NP%5F%28complexity%29
http://en.wikipedia.org/wiki/NP-complete
http://en.wikipedia.org/wiki/Np-hard

Answer 2

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%5F%28complexity)

Answer 3

I assume that you are looking for intuitive definitions (the technical definitions are, well, technical and require quite some time to understand). Let's start by defining NP.

Decision problem: A question with a yes or no answer.

P: A decision problem that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.

Example: Given a graph G, can its vertices be colored using two colors so that no edge is monochromatic. Algorithm: start with an arbitrary vertex, color it red and all of its neighbors blue and continue. Stop when you run our of vertices or you are forced to make an edge have both of its endpoints be the same color.

NP: A decision problem where instances of the problem for which the answer is yes have proofs that can be verified in polynomial time. This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) so the answer being yes, we can check that it is correct in polynomial time.

Example: Integer factorization is NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m such that f divides n (f is a small factor of n)? This is a decision problem because the answers are yes or no. If someone hands us an instance of the problem (so they hand us integers n and m) and an integer f with 1 < f < m and claim that f is a factor of n (the certificate) we can check the answer in polynomial time by performing the division n / f.

NP-complete: An NP problem X for which it is possible to reduce any other NP problem Y to X in polynomial time. Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X if there is a polynomial time algorithm f to transform instances x of X to instances y=f(x) of Y in polynomial time with the property that the answer to x is yes if and only if the answer to f(x) is yes.

Example: 3-SAT. This is the problem wherein we are given a conjunction of 3-clause disjunctions (i.e., statements of the form

(x_v11 or x_v21 or x_v31) and (x_v12 or x_v22 or x_v32) and ... and (x_v1n or x_v2n or x_v3n)

where each x_vij is a variable or the negation of a variable from a finite predefined list (x_1, x_2, ... x_n). It can be shown that every NP problem can be reduced to 3-SAT. The proof of this is technical and requires use of the technical definition of NP (based on non-deterministic Turing machines and the like). This is known as Karp's theorem.

What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).

NP-hard: Intuitively these are the problems that are even harder than the NP-complete problems. Note that NP-hard problems do not have to be in NP (they do not have to be decision problems). The precise definition here is that a problem X is NP-hard if there is an NP-complete problem Y such that Y is reducible to X in polynomial time. But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.

The halting problem is the classic NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one.

P = NP: This the most famous problem in computer science, and one of the most important outstanding questions in the mathematical sciences. In fact, the Clay Institute is offering one million dollars for a solution to the problem (Stephen Cook's writeup on the Clay website is quite good). It's clear that P is a subset of NP. The open question is whether or not NP problems have deterministic polynomial time solutions. It is largely believed that they do not. Here is an outstanding recent article on the latest (and the importance) of the P = NP problem: The Status of the P versus NP problem.

The best book on the subject is Computers and Intractability by Garey and Johnson. My favorite NP-complete problem is the Minesweeper problem.

Answer 4

This is a very informal answer to the question asked.

Can 3233 be written as the product of two other numbers bigger than 1? Is there any way to walk a path around all of the Seven Bridges of Königsberg without taking any bridge twice? These are examples of questions that share a common trait. It may not be obvious how to efficiently determine the answer, but if the answer is 'yes', then there's a short and quick to check proof. In the first case a non-trivial factorization of 51; in the second, a route for walking the bridges (fitting the constraints).

A decision problem is a collection of questions with yes or no answers that vary only in one parameter. Say the problem COMPOSITE={"Is n composite": n is an integer} or EULERPATH={"Does the graph G have an Euler path?": G is a finite graph}.

Now, some decision problems lend themselves to efficient, if not obvious algorithms. Euler discovered an efficient algorithm for problems like the "Seven Bridges of Königsberg" over 250 years ago.

On the other hand, for many decision problems, it's not obvious how to get the answer -- but if you know some additional piece of information, it's obvious how to go about proving you've got the answer right. COMPOSITE is like this: Trial division is the obvious algorithm, and it's slow: to factor a 10 digit number, you have to try something like 100,000 possible divisors. But if, for example, somebody told you that 61 is a divisor of 3233, simple long division is a efficient way to see that they're correct.

The complexity class NP is the class of decision problems where the 'yes' answers have short to state, quick to check proofs. Like COMPOSITE. One important point is that this definition doesn't say anything about how hard the problem is. If you have a correct, efficient way to solve a decision problem, just writing down the steps in the solution is proof enough.

Algorithms research continues, and new clever algorithms are created all the time. A problem you might not know how to solve efficiently today may turn out to have an efficient (if not obvious) solution tomorrow. In fact, it took researchers until 2002 to find an efficient solution to COMPOSITE! With all these advances, one really has to wonder: Is this bit about having short proofs just an illusion? Maybe every decision problem that lends itself to efficient proofs has an efficient solution? Nobody knows.

Perhaps the biggest contribution to this field came with the discovery a peculiar class of NP problems. By playing around with circuit models for computation, Stephen Cook found a decision problem of the NP variety that was provably as hard or harder than every other NP problem. An efficient solution for the boolean satisfiability problem could be used to create an efficient solution to any other problem in NP. Soon after, Richard Karp showed that a number of other decision problems could serve the same purpose. These problems, in a sense the "hardest" problems in NP, became known as NP-complete problems.

Of course, NP is only a class of decision problems. Many problems aren't naturally stated in this manner: "find the factors of N", "find the shortest path in the graph G that visits every vertex", "give a set of variable assignments that makes the following boolean expression true". Though one may informally talk about some such problems being "in NP", technically that doesn't make much sense -- they're not decision problems. Some of these problems might even have the same sort of power as an NP-complete problem: an efficient solution to these (non-decision) problems would lead directly to an efficient solution to any NP problem. A problem like this is called NP-hard.