What is an NP-complete in computer science?

algorithm language-agnostic mathematical-optimization theory np-complete
Claudiu picture Claudiu · Oct 17, 2008 · Viewed 262.6k times · Source

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

Answer

grom picture grom · Nov 24, 2008

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(nk) 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.

Related questions

3 dimensional bin packing algorithms

I'm faced with a 3 dimensional bin packing problem and am currently conducting some preliminary research as to which algorithms/heuristics are currently yielding the best results. Since the problem is NP hard I do not expect to find the optimal …

Read More
What is tail recursion?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?

Read More
How do you detect Credit card type based on number?

I'm trying to figure out how to detect the type of credit card based purely on its number. Does anyone know of a definitive, reliable way to find this?

Read More