NP-Complete Problem — Definition, Formula & Examples

An NP-Complete problem is a decision problem that is both in NP (a proposed solution can be verified quickly) and as hard as every other problem in NP, meaning any NP problem can be transformed into it in polynomial time.

A decision problem $L$ is NP-complete if (1) $L \in \text{NP}$ , meaning a certificate for any yes-instance can be verified by a deterministic Turing machine in polynomial time, and (2) for every problem $L' \in \text{NP}$ , there exists a polynomial-time many-one reduction $L' \leq_p L$ .

How It Works

To prove a problem

Q

is NP-complete, you do two things. First, show

Q \in \text{NP}

by describing a polynomial-time verifier that checks a candidate solution. Second, pick a known NP-complete problem

R

and construct a polynomial-time reduction from

R

Q

, so that every instance of

R

maps to a corresponding instance of

Q

preserving yes/no answers. This chain of reductions started historically with the Cook–Levin theorem, which proved that Boolean satisfiability (SAT) is NP-complete. Since then, hundreds of problems have been shown NP-complete by reducing from SAT or from other already-proven NP-complete problems.

Example

Problem: Show that the Vertex Cover problem is in NP, given that a certificate is a set of vertices.

Step 1: A Vertex Cover instance asks: given a graph

G = (V, E)

and integer

k

, is there a subset

S \subseteq V

with

|S| \leq k

such that every edge in

E

has at least one endpoint in

S

Step 2: Given a candidate set

S

, a verifier checks two things: that

|S| \leq k

, and that for each edge

(u, v) \in E

, at least one of

u

v

is in

S

. Both checks run in polynomial time.

Step 3: Since a certificate can be verified in polynomial time, Vertex Cover is in NP. Combined with a known polynomial-time reduction from an existing NP-complete problem (e.g., 3-SAT

\leq_p

Vertex Cover), Vertex Cover is NP-complete.

Answer: Vertex Cover is in NP because any proposed vertex set can be checked in

O(|E|)

time. A reduction from 3-SAT completes the NP-completeness proof.

Why It Matters

NP-completeness is central to algorithm design: once you recognize a problem as NP-complete, you know that no known polynomial-time algorithm solves it, so you pivot to approximation algorithms, heuristics, or special-case solutions. The open question of whether

P = NP

— whether these hard problems actually have efficient solutions — is one of the most important unsolved problems in mathematics and computer science.

Common Mistakes

Mistake: Saying NP-complete problems are 'unsolvable' or 'impossible to solve'.

Correction: NP-complete problems can be solved; they just have no known polynomial-time algorithm. Exponential-time algorithms, backtracking solvers, and approximation methods handle them in practice.