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:

It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". Each input to the problem is associated with a collection of short (polynomial size) 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. 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. 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.

Formal definition and related complexity classes

A decision problem C {\displaystyle \scriptstyle C} is NP-complete if:

C {\displaystyle \scriptstyle C} is in NP, and Every problem in NP is reducible to C {\displaystyle \scriptstyle C} in polynomial time.

C {\displaystyle \scriptstyle C} can be shown to be in NP by demonstrating that a candidate solution to C {\displaystyle \scriptstyle C} can be verified in polynomial time. A decision problem that is solvable in polynomial time belongs to the class P. All problems in P are necessarily in NP. However, it has not been proved that the class NP is actually larger than P. In other words, it is not yet known whether there exist problems in NP that are not in P. The question of whether the classes P and NP are equal or not is known as the P versus NP problem. A consequence of the definition of NP-completeness is that if we had a polynomial-time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for C {\displaystyle \scriptstyle C} , we could solve all problems in NP in polynomial time. A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. A problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems are thus, in a sense, the hardest problems in NP.

Known NP-complete problems

The Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete, establishing for the first time that such problems do exist. In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems); thus, there is a class of NP-complete problems, besides Boolean satisfiability. Since these original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey & Johnson (1979). The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. The list below contains some well-known problems that are NP-complete when expressed as decision problems.

… excerpt ends here. Continue reading the full article.