NP-Complete Problem

Definition

An NP-complete problem is a decision problem that is both in the complexity class NP (its solutions can be verified quickly) and is at least as hard as every other problem in NP, meaning an efficient algorithm for one NP-complete problem would yield an efficient algorithm for all of them.

Overview

NP-complete problems sit at the center of one of the most important open questions in Computational Complexity theory: whether P equals NP. The class P contains problems solvable efficiently (in polynomial time), while NP contains problems whose proposed solutions can be verified efficiently, even if no efficient way to find that solution is known. A problem is NP-complete if it belongs to NP and every other problem in NP can be transformed ('reduced') into it in polynomial time — making NP-complete problems the hardest problems within NP. The first problem proven NP-complete was Boolean satisfiability (SAT), shown by Stephen Cook in 1971 (and independently by Leonid Levin), establishing the theoretical foundation that many other well-known problems — including the traveling salesman problem, the knapsack problem, graph coloring, and subset sum — were later shown to be NP-complete by reduction from SAT or from each other. If anyone ever finds a polynomial-time algorithm for even one NP-complete problem, it would prove P = NP and immediately imply that every NP-complete problem is efficiently solvable, a discovery with enormous theoretical and practical implications, including breaking most modern cryptography. In practice, because no polynomial-time algorithm is known for any NP-complete problem, real-world systems facing them rely on approximation algorithms, heuristics, or exact solvers that perform well on typical inputs despite worst-case exponential behavior. Recognizing that a problem is NP-complete is itself practically useful: it signals to engineers that they should stop searching for an efficient exact algorithm and instead invest in heuristics or accept approximate solutions. It is often mentioned alongside Turing Machine in this space. It is often mentioned alongside Halting Problem in this space.

Key Concepts

• Belongs to the complexity class NP: proposed solutions can be verified in polynomial time
• Every problem in NP can be reduced to it in polynomial time, making it maximally hard within NP
• First shown to exist by the Cook-Levin theorem using Boolean satisfiability (SAT)
• No known polynomial-time algorithm exists for solving any NP-complete problem
• Whether P = NP remains one of the most famous unsolved problems in mathematics
• Includes well-known problems like traveling salesman, knapsack, and graph coloring
• Practical solutions typically rely on approximation algorithms or heuristics
• Directly relevant to cryptography, since some security assumptions rely on certain problems being hard

Use Cases

Frequently Asked Questions

Related in Computer Science