NP-completeness

In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. Somewhat more precisely, a problem is NP-complete when:

1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
2. Each input to the problem is associated with a collection of short (polynomial length) solutions, which might or might not validly solve the input. The output is "yes" when at least one of these solutions is valid, and "no" when none of them are.
3. The validity of each solution can be verified quickly (namely, in polynomial time), and a brute-force search algorithm can find a valid solution (if one exists) by trying all possible solutions.
4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is valid. Hence, if we could find valid solutions of some NP-complete problem quickly (when they exist), we could quickly find valid solutions for every other problem in which a given solution can be easily verified.

Problems that meet the first three criteria belong to the class NP, which is short for "nondeterministic polynomial-time". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. A problem that is in NP and also meets the fourth criterion is said to be "NP-complete". The term "complete" refers to the property of being able to simulate everything in the same complexity class: If some NP-complete problem has a polynomial time algorithm, all problems in NP do.

The set of NP-complete problems is often denoted by NP-C or NPC.

Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the fundamental unsolved problems in computer science today.

While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms.