NP-Complete — Definition, Formula & Examples

NP-Complete is a classification for decision problems that are both in NP (verifiable in polynomial time) and at least as hard as every other problem in NP. If any single NP-Complete problem could be solved efficiently, then every problem in NP could be solved efficiently.

A decision problem $L$ is NP-Complete if (1) $L \in \text{NP}$ , meaning any "yes" instance has a certificate verifiable by a deterministic Turing machine in polynomial time, and (2) every problem $L' \in \text{NP}$ is polynomial-time reducible to $L$ (i.e., $L' \leq_p L$ ). This definition was formalized by Stephen Cook (1971) and Richard Karp (1972).

How It Works

To prove a problem

Q

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

Q \in \text{NP}

by demonstrating that a proposed solution can be checked in polynomial time. Second, take a known NP-Complete problem

R

and construct a polynomial-time reduction from

R

Q

, written

R \leq_p Q

. This reduction transforms any instance of

R

into an instance of

Q

such that the answer is preserved. If both steps succeed,

Q

is NP-Complete. The SAT problem (Boolean satisfiability) was the first problem proven NP-Complete, and most new proofs reduce from an already-known NP-Complete problem like SAT, 3-SAT, or CLIQUE.

Example

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

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

G = (V, E)

and an integer

k

, does there exist a set

S \subseteq V

with

|S| \leq k

such that every edge in

E

has at least one endpoint in

S

? The certificate is the set

S

itself.

Step 2: To verify, check that

|S| \leq k

(takes

O(|V|)

time) and that for every edge

(u,v) \in E

, at least one of

u

v

is in

S

(takes

O(|E|)

time).

Step 3: Total verification time is

O(|V| + |E|)

, which is polynomial. Therefore Vertex Cover is in NP. Combined with a known polynomial-time reduction from 3-SAT to Vertex Cover, this establishes Vertex Cover as NP-Complete.

Answer: Vertex Cover is in NP because a proposed solution can be verified in

O(|V| + |E|)

time, which is polynomial.

Why It Matters

NP-Completeness is central to algorithm design courses and theoretical computer science. When you prove a problem is NP-Complete, you know that no known polynomial-time algorithm exists for it, which guides you toward approximation algorithms or heuristics instead. This classification directly impacts fields like operations research, cryptography, and computational biology where hard optimization problems arise constantly.

Common Mistakes

Mistake: Confusing NP with "not polynomial" or "exponential time."

Correction: NP stands for "nondeterministic polynomial time" — it means a solution can be verified quickly, not that the problem necessarily requires exponential time to solve. In fact, every problem in P is also in NP.