NP-completeness

Lore & Background

NP-complete problems are decision problems where each input has a collection of short (polynomial-size) candidate solutions, and the output is 'yes' if at least one solution is valid. The validity of each solution can be verified quickly (in polynomial time), and a brute-force search can find a valid solution by trying all possibilities. Problems meeting these criteria belong to the class NP, which stands for 'nondeterministic polynomial-time,' referencing nondeterministic Turing machines that formalize brute-force search.

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.