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

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 from what's out there, or there is something that I'm not aware of.

Solution 1

I assume that you are looking for intuitive definitions, since the technical definitions require quite some time to understand. First of all, let's remember a preliminary needed concept to understand those definitions.

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

---

Now, let us define those complexity classes.

P

P is a complexity class that represents the set of all decision problems 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 connected graph G, can its vertices be coloured using two colours so that no edge is monochromatic?

Algorithm: start with an arbitrary vertex, color it red and all of its neighbours blue and continue. Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color.

---

NP

NP is a complexity class that represents the set of all decision problems for which the instances where 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) to the answer being yes, we can check that it is correct in polynomial time.

Example

Integer factorisation is in 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

NP-Complete is a complexity class which represents the set of all problems X in NP 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 y of Y to instances x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes.

Example

3-SAT. This is the problem wherein we are given a conjunction (ANDs) of 3-clause disjunctions (ORs), 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 boolean 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). This is known as Cook'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 at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and 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.

Example

The halting problem is an 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. As another example, any NP-complete problem is NP-hard.

My favorite NP-complete problem is the Minesweeper problem.

---

P = NP

This one is 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.

Solution 2

I've been looking around and seeing many long explanations. Here is a small chart that may be useful to summarise:

Notice how difficulty increases top to bottom: any NP can be reduced to NP-Complete, and any NP-Complete can be reduced to NP-Hard, all in P (polynomial) time.

If you can solve a more difficult class of problem in P time, that will mean you found how to solve all easier problems in P time (for example, proving P = NP, if you figure out how to solve any NP-Complete problem in P time).

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Notes on Yes or No entries:

• * An NP problem that is also P is solvable in P time.
• ** An NP-Hard problem that is also NP-Complete is verifiable in P time.
• *** NP-Complete problems (all of which form a subset of NP-hard) might be. The rest of NP hard is not.

I also found this diagram quite useful in seeing how all these types correspond to each other (pay more attention to the left half of the diagram).

Solution 3

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.

Solution 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 61 (53 being the other prime factor); 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.

Solution 5

In addition to the other great answers, here is the typical schema people use to show the difference between NP, NP-Complete, and NP-Hard:

View more solutions

Comments

[San Jacinto]

Not that I see anything in this answer that is incorrect, but I don't know why it was accepted. It doesn't really offer much to what the OP was asking. It's not really even different than the standard explanations of these problems, and there aren't any clear explanations as to what makes these problems in these classes. Not worth a downvote, but certainly not worth answer acceptance.

[DarthVader]

upvote for San. to appreciate an answer. this is what i was looking a short summary of what someone thinks. there are much more interesting approaches i read. such as Non-deterministic turing machine and the way it works to explain the problem. i just wanted to see an answer without going too deep into details. such as a magic machine that works non deterministically in paralel and solves problems in polinomial time which these problems are NP problems.

[DarthVader]

Yet another example is dove tailing, a paradigm in parallel programming which describes NP problems.

[DarthVader]

decision trees are another tool to use to explain NP problems.

[jason]

@unknown (google): The explanations involving non-deterministic Turing machines are the technically correct explanations. Turing machines are how we formalize the notions of computers, algorithms, problems etc.

[Managu]

NP-hard problems need not be decision problems

[jason]

@Managu: Yes, that is what I meant when I said that "NP-hard problems do not have to be in NP." I will make this meaning more explicit.

[jason]

@Paul Fisher: I'll show that SAT is reducible to the halting problem in polynomial time. Consider the following algorithm: given as input a proposition I over n variables, try all 2^n possible assignments to the variables and halt if one satisfies the proposition and otherwise enter an infinite loop. We see that this algorithm halts if and only if I is satisfiable. Thus, if we had a polynomial time algorithm for solving the halting problem then we could solve SAT in polynomial time. Therefore, the halting problem is NP-hard.

[rjzii]

@Jason - You can't reduce a decidable problem to an undecidable problem in that manner. Decidable problems have to result in a definitive yes or no answer in order to be considered to be decidable. The Halting Problem does not have a definitive yes or now answer since an arbitrary answer might throw any solution into a loop.

[jason]

@Rob: Yes, I can. The definition of reducible does not require that the problem being reduced to be solvable. This is true for either many-one reductions or Turing reductions.

[rjzii]

@Jason - Sorry, that's wrong even though I must admit that I was incorrect in stating that the Halting problem doesn't have a definitive yes or no solution. It is indeed a decision problem; however, it is an undecidable one. The reason that you can't reduce SAT to the Halting problem in that way is because the Halting problem requires that a Turing Machine M and a input string w be provided, it should then accept if M accepts w, otherwise reject. However, simulation of M on a Universal Turing Machine might cause a loop which is why the Halting Problem is undecidable.

[rjzii]

[continued] Likewise, you fail to provide a mapping from SAT to the Halting problem since you are, in essence, saying that any Boolean formula can be used to determine if M accepts w however, this is not possible unless you have a means of simulating M which you fail to provide.

[jason]

@Rob: Well, okay, if you want to continue this. First, "Decidable" is not synonomous with "decision problem" as you've used it. "Decidable" means, roughly, that there is an "effective method" for determining the answer. "Effective method", of course, has a technical definition. Moreover, "decidable" can also be defined in terms of "computable functions." So, the halting problem is a decision problem ("Does this program halt?" is a yes/no question) but it is undecidable; there is no effective method for determining whether or not an instance of the halting problem will halt.

[jason]

@Rob: Second, I maintain that the definition of reducibility does not require that the problem being reduced to be decidable. Precisely, we say that A is Turing reducible to B if there is an Oracle algorithm for A given an Oracle algorithm for B. See, for example, Sipser, Introduction to the Theory of Computation.

[jason]

@Rob: Finally, regarding the statement that started all of this ("the halting problem is NP-hard"), I note that Google (google.com/…) turns up several links (including Wikipedia and multiple professor's course pages) asserting as much; some even provide proofs similar to the one that I outlined.

[rjzii]

@Jason - Just so you know, I'm not "continuing this" to be a jerk or anything, these are subjects that I enjoy talking about. Now, back to the subject at hand, I did some reading around and it seems that the problem is we are both slightly in disagreement in regards to how we are defining reducibility. I've been exposed to in such a way that you should be able to reciprocate the reduction such that if you go from A to B then you should be able to go from B to A, likewise this is the definition that is been used in the formal class I took on the subject.

[rjzii]

[continued] However, there is another type of reduction ("many-one reduction") that is a simple A to B with no guarantee of going the other direction and it seems that is what you are using in your proof sketch.

[jason]

@Rob: I never took you to be a jerk. I'm here to learn too and discussing this stuff is fun. And yes, I was only using one-direction reducibility.

[Admin]

I am surprised there is no mention of Cook's theorem in this answer :-)

[Patrick87]

@Jason Nice post. One downside of using the Halting Problem as an example NP-Hard problem is that it might give students the (possibly mistaken) impression that all problems not in NP are NP-hard - which is only true (of non-trivial problems) if P = NP. If P != NP, there are problems not in NP which are not NP-hard.

[phimuemue]

I think "Computational Complexity" (amazon.de/Computational-Complexity-Christos-H-Papadimitriou‌​/dp/…) is also quite a good book.

[Srikanth]

I've a doubt related to your answer. I asked it in a separate question, but I was asked to post it here. Can you please help me here? stackoverflow.com/questions/21005651/…

[Falk Hüffner]

It is unknown whether NP-complete problems are solvable in polynomial time. Also, NP-complete problems are NP-hard, so some NP-hard problems are verifiable in polynomial time, and possible some also polynomial-time solvable.

[Michael]

This table is incorrect and self-contradictory. Even if you assume that NP!=P, which has not been proved yet, it would still be incorrect. For example, NP-Hard class includes NP-Complete problems; therefore your table claims that NP-Complete problems are simultaneously verifiable in polynomial time and not verifiable in polynomial time.

[Johnson Wong]

@FalkHüffner Thanks, table is updated (was an error in translating from the Venn diagram).

[Michael]

Using Halting problem as a "classic example" of NP-hard problem is incorrect. This is like saying: "Pacific Ocean is a classic example of a salt water aquarium."

[Nuri Tasdemir]

Isn't this part "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" should be "Precisely, Y is reducible to X if there is a polynomial time algorithm f to transform instances y of Y to instances x = f(y) of X in polynomial time with the property that the answer to y is yes if and only if the answer to f(y) is yes"

[DodoSombrero]

If an example of an NP-Hard Problem is needed, a SAT Solver according to Cook is the hardest problem in NP. If that can be solved in Polynomial time, then EVERY NP problem can be solved in Polynomial time

[Hilder Vitor Lima Pereira]

Is it proven that there exist a problem in NP-Hard that is not in NP-Complete? Because this image suggests it. Thank you.

[Franck Dernoncourt]

@VitorLima yes e.g. EXPSPACE-complete problems are NP-hard but proven not to be NP-complete.

[Hilder Vitor Lima Pereira]

Ok, thank you. I found some references talking about it. For example, this one: princeton.edu/~achaney/tmve/wiki100k/docs/NP-hard.html

[Peter Raeves]

I'm confused about your second comment. How can a problem be both NP-Hard as NP-Complete? Could you give me an example?

[Peter Raeves]

Sorry, but I don't understand your first comment either. How can a problem be both NP (not solvable in polynomial time) and at the same time P (solvable in polynomial time?)

[Khaled.K]

So the bottom line is that if you can solve TSP in Polynomial Time, you can prove P = NP

[Jim Balter]

@PeterRaeves All NP-complete problems are NP-hard, by definition: NP-complete = (NP and NP-hard). The inverse is not true: there are problems (such as the Halting Problem) in NP-hard that are not in NP-complete. "NP (not solvable in polynomial time) " -- that's not what NP means. NP is "Non-deterministic-polynomial". All problems in P are also in NP. Whether the inverse is true is famously unknown.

[Jim Balter]

Your understanding is incorrect. Your definition of NP-complete is correct but has no bearing on your first statement. All problems in NP-hard are at least as hard as those in NP-complete; some (e.g. the Halting Problem, which is infinitely hard, and en.wikipedia.org/wiki/EXPSPACE) are provably harder.

[Hayden]

The usage of the Halting Problem is incorrect. It has been proven that no computer can COMPUTE the Halting Problem.

[Jeremy List]

@Hayden uncomputable problems are classified as NP-Hard

[John Red]

I was genuinely amazed when I found that Wikipedia's article on NP-Completeness was surprisingly easy to understand.

[Cœur]

You could replace Unknown *** by Unknown or No *** in your table, to highlight there are multiple situations, some of those with a known difficulty.

[meaning-matters]

Best answer as it's short, uses just enough terminology, has normal human sentences (not the hard to read let's-be-as-correct-as-possible stuff), and surprisingly enough is the only answer that writes what N stands for.

[user2399453]

In the integer factorization case why do we care to have two numbers n and m? Why is it not just n and f and the check will be to see if f divides n in polynomial time?

[Björn Lindqvist]

What is the source for the image?

[Alexandre M]

Thanks for that. The old link is broken, though. The new address of that site is complexityzoo.net/Complexity_Zoo

[Joker]

In your answer, the cell for ("NP", "Solvable in P time") reads Yes or No *. Does this have to do with the famous, millionaire problem P=?=NP. If I understand your answer right, assuming the cell should read 'Yes' then implies, P=NP. Assuming the cell reads No then implies, P!=NP. Of course we do not know for sure as P=?=NP is still an open problem. Is that it?