NP-completeness

Lore & Background

NP-complete problems are decision problems, meaning their output is always either "yes" or "no." For any given input, there exists a collection of candidate solutions whose size is polynomial relative to the input. The answer is "yes" if at least one of these candidates is a valid solution, and "no" otherwise. Crucially, the validity of any candidate solution can be verified quickly—specifically, in polynomial time. A brute-force search algorithm, which tries all possible candidates, can find a valid solution if one exists. Problems satisfying these three conditions belong to the complexity class NP, a name derived from "nondeterministic polynomial-time." This term references nondeterministic Turing machines, a mathematical model that formalizes the concept of brute-force search, while "polynomial time" describes the quickness required for checking a single solution or for the nondeterministic machine to complete the search. A problem is NP-complete if it is in NP and also meets a fourth condition: it can be used to simulate every other problem in NP. This means that if a fast (polynomial-time) method were found for any NP-complete problem, it would yield a fast method for all problems in NP. The set of NP-complete problems is often denoted NP-C or NPC. Despite the ability to verify solutions quickly, no known algorithm can find solutions quickly; the required time grows rapidly with problem size. This unsolved question of whether quick solutions exist is known as the P versus NP problem. In practice, NP-complete problems are frequently encountered and are addressed using heuristic methods and approximation algorithms. The existence of such problems was first established by the Cook–Levin theorem, which proved Boolean satisfiability (SAT) is NP-complete. Subsequently, many other problems—including the knapsack problem, Hamiltonian path problem, travelling salesman problem (decision version), subgraph isomorphism, subset sum, clique, vertex cover, independent set, dominating set, graph coloring, and Sudoku—have been shown to be NP-complete through reductions from previously proven NP-complete problems.

Reader's Guide

The significance of NP-completeness lies in its role as a cornerstone of the P versus NP problem. If any NP-complete problem could be solved quickly (in polynomial time), then all problems in NP could be solved quickly, implying P equals NP. Conversely, if P does not equal NP, then NP-complete problems are inherently hard. Despite no known fast algorithms, NP-complete problems are frequently encountered in practice and are addressed using heuristic methods, approximation algorithms, restriction, and parameterization. The Cook–Levin theorem first established the existence of NP-complete problems via the Boolean satisfiability problem, and Richard Karp later proved many others. Thousands of problems have since been shown NP-complete through reductions. The concept also distinguishes NP-hard problems (which are at least as hard as NP-complete but may not be in NP) and NP-intermediate problems (suspected to be neither in P nor NP-complete, existing only if P≠NP).

Did You Know?

• A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time.
• The Cook–Levin theorem proved that the Boolean satisfiability problem is NP-complete, establishing the first such problem.
• If any NP-complete problem has a polynomial-time algorithm, then all problems in NP do.
• The graph isomorphism problem is suspected to be neither in P nor NP-complete, making it a candidate NP-intermediate problem.