What is an NP-complete in computer science?

Question

What is an NP-complete problem? Why is it such an important topic in computer science?

Solution 1

NP stands for Non-deterministic Polynomial time.

This means that the problem can be solved in Polynomial time using a Non-deterministic Turing machine (like a regular Turing machine but also including a non-deterministic "choice" function). Basically, a solution has to be testable in poly 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.

The main thing to take away from an NP-complete problem is that it 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.

Edit: As others have noted, there are often approximate solutions for NP-Complete problems. In this case, the approximate solution usually gives an approximation bound using special notation which tells us how close the approximation is.

Solution 2

What is NP?

NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(n^k) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.

What is P?

P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.

What is NP-Complete?

A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.

In other words:

1. x is in NP, and
2. Every problem in NP is reducible to x

So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.

See also the post What's "P=NP?", and why is it such a famous question?

What is NP-Hard?

NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.

Solution 3

NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that

1. There is polynomial-time proof for every instance of the problem with a "yes" answer that the answer is "yes", or (equivalently)
2. There exists a polynomial-time algorithm (possibly using random variables) that has a non-zero probability of answering "yes" if the answer to an instance of the problem is "yes" and will say "no" 100% of the time if the answer is "no." In other words, the algorithm must have a false-negative rate less than 100% and no false positives.

A problem X is NP-Complete if

1. X is in NP, and
2. For any problem Y in NP, there is a "reduction" from Y to X: a polynomial-time algorithm that transforms any instance of Y into an instance of X such that the answer to the Y-instance is "yes" if and only if the answer X-instance is "yes".

If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).

So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.

Solution 4

Basically this world's problems can be categorized as

         1) Unsolvable Problem          2) Intractable Problem          3) NP-Problem          4) P-Problem

---

         1)The first one is no solution to the problem.          2)The second is the need exponential time (that is O (2 ^ n) above).          3)The third is called the NP.          4)The fourth is easy problem.

---

P: refers to a solution of the problem of Polynomial Time.

NP: refers Polynomial Time yet to find a solution. We are not sure there is no Polynomial Time solution, but once you provide a solution, this solution can be verified in Polynomial Time.

NP Complete: refers in Polynomial Time we still yet to find a solution, but it can be verified in Polynomial Time . The problem NPC in NP is the more difficult problem, so if we can prove that we have P solution to NPC problem then NP problems that can be found in P solution.

NP Hard: refers Polynomial Time is yet to find a solution, but it sure is not able to be verified in Polynomial Time . NP Hard problem surpasses NPC difficulty.

Solution 5

NP-Complete is a class of 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.

The class NP consists of those problems that are verifiable in polynomial time. That is, if we are given a potential solution, then we could check if the given solution is correct in polynomial time.

Some examples are the Boolean Satisfiability (or SAT) problem, or the Hamiltonian-cycle problem. There are many problems that are known to be in the class NP.

NP-Complete means the problem is at least as hard as any problem in NP.

It is important to computer science because it has been proven that any problem in NP can be transformed into another problem in NP-complete. That means that a solution to any one NP-complete problem is a solution to all NP problems.

Many algorithms in security depends on the fact that no known solutions exist for NP hard problems. It would definitely have a significant impact on computing if a solution were found.

View more solutions

Comments

[csakii]

Almost right. A problem can have a non-exhaustive solution that's still not polynomial in nature.

[David Nehme]

this is wrong. A problem in NP can be transformed into any problem in NP-complete, not any problem in NP. That's a big difference.

[quick_dry]

I have discovered a truly marvellous proof of this, which this comment is too narrow to contain ;)

[Chris Conway]

Condition #2 is a statement of P=?NP, not the standard definition of NP-completeness. It should be: a deterministic poly-time algorithm exists that can transform any other NP instance X into an instance Y of this problem s.t. the answer to Y is "yes" if and only if the answer to X is "yes".

[Windows programmer]

"you have to be careful or you will get the definition wrong" -- as proven by this very answer. This answer is partly right but it sure shouldn't have been accepted.

[Windows programmer]

The O() notation tells us how fast (or how slow) the approximation solution runs, but other notations tell us how close we think the approximation is probably somewhat likely to be.

[Windows programmer]

Also, "the problem is as hard as any problem in NP" -- true, but better wording would be "at least as hard". Overall, this answer comes closer than any other answer I've seen, and closer than the unfortunately accepted answer.

[leo7r]

"... an NP problem can be reduced to the given problem ..." - an important constraint on the reduction is that it should be deterministically polynomial.

[Chris Conway]

A fair point. My guess is any proof that P = NP is likely to be constructive though (e.g., the publication of a polynomial algorithm for 3-SAT).

[Vincent Ramdhanie]

Thank you for your observations. I have updated the answer tio include your corrections.

[Jonathan Adelson]

Fixed the approximation notation bug. thanks, windows programmer.

[LvMan3]

The O() notation is a general mathematical notation used everywhere: approximation algorithms are indeed given to O() accuracy -- look up any approximation algorithm paper on arxiv.org

[Yuval Adam]

No need to confuse the answer. Any language is decidable by a DTM iff it is decidable by a NDTM. I'm editing to answer for clarity.

[rjzii]

To clarify a bit, NP problems are referencing non-deterministic Turing machines. It is still unknown if a NP-complete problem can be solved in polynomial time on a deterministic Turing machine.

[sepp2k]

"That is the NP in NP-hard does not mean non-polynomial" <- The NP in NP-complete (or anywhere else) doesn't mean non-polynomial either.

[grom]

Thanks sepp2k for the correction. I meant to say it doesn't mean NP (ie non-deterministic polynomial time).

[Admin]

@Yuval: DTM and NDTM are different (at least wrt time complexity). Your edit proved that P=NP!

[Yuval Adam]

@Moron - you are wrong. en.wikipedia.org/wiki/… please rollback your change.

[Admin]

@Yuval what are you talking about? While it is true that the set of all languages accepted by a DTM is same as set of all languages accepted by a NDTM, is the set of languages accepted by a DTM in time O(n) (n is size of input) same as the set of languages accepted by NDTM in O(n) time? P is the set of languages accepted by a DTM in polynomial time in size of input. NP is the set of languages accepted by a NDTM in polynomial time in size of input. P=NP is the question whether these two are the same.

[Yuval Adam]

N/DTMs are equivalent. However, since the answer does deal with DTMs and NDTMs in relation to time complexity, I accept your rollback. Fair enough.

[Admin]

@Yuval: Just to make it clear. What you had earlier was completely wrong(unless P=NP). From your comment I get the feeling that you think both versions were right. If not, I apologize.

[Adam Zalcman]

"[If a problem is NP] and a known NP problem can be solved using the given problem with modified input [...] then the problem is NP complete" is incorrect. A problem is NP-complete if it's NP and all other NP problems can be reduced to it. Alternatively, a problem is NP-complete if it's NP and another NP-complete problem can be reduced to it.

[SoftwareSavant]

I think your answer simplifies as much or more than others in this thread. But this is still a very hard problem for me to grasp... Guess that is why they pay algorithm guys the big bucks.

[grom]

@DmainEvent, which part are you having trouble grasping? For example of NP-Complete problems checkout en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems in particular Knapsack problem. Hope that helps.

[hqt]

About NP : I think it should be : The problem can be solve by nondeterministic Turing machine. (nonderterministic rather than derministic)

[grom]

@hqt What I wrote is correct.. Notice the word "verified". You are also correct, NP can be solved in polynomial time by non-deterministic Turing machine

[doug65536]

Although not exactly right, this is close enough for practical use. The pedantic definition is not necessary although the OP probably wants the pedantic definition. It's a good approximation!

[nbro]

This answer is far from complete and understandable, and I cannot understand why it has so many upvotes.

[nbro]

@grom This answer is more a summary of the most famous complexity classes than explaining exhaustively what NP-Complete problems are. So, I will downvote, even if this answer is really nice, but for another question.

[nbro]

Your definition of NP-Complete is not complete, you need also to specify that NP-Complete problems are also NP (and NP-hard) problems and not just as hard as any NP problems. I will downvote, if you decide to change, make me know and I remove the downvote.

[DubiousPusher]

Perhaps I'm confused by the other explanations here but shouldn't this read "ANY NP problem can be reduced to a 3-SAT problem in polynomial time." Because isn't that what makes 3-SAT NP-Complete?

[PeerNet]

Glad to see this answer, the categorization part is quite expressive for whole concept. I thought interactable problems are NP-Problems.

[Cyriac Antony]

@RafałDowgird Reduction is used as a synonym for polynomial transformation by many authors including Garey and Johnson.

[Branden Keck]

Quick question about your stages... can't the verification stage be deterministic? Aren't NP problems verified in P-time

[hashlash]

I think you should put @hqt comment to your answer to help people understand the nondeterministic part of Nondeterministic Polynomial.

[jayeshsolanki93]

@DubiousPusher Nope. The answer states it correctly. This image clarifies it stackoverflow.com/a/7367561/2686502