NP-completeness

Builds on NP NP-hardness Polynomial-time reduction Formal language P

Definition

Let $\Sigma$ be a finite alphabet, and let $C \subseteq \Sigma^*$ be a language. The language $C$ is NP-complete when both conditions hold.

$C$ lies in the class NP.
$C$ is NP-hard, that is, $A \le_p C$ for every $A \in \mathrm{NP}$ , where $\le_p$ is polynomial-time reducibility.

Remarks

Example: the satisfiability problem SAT for propositional formulas is NP-complete, by the Cook–Levin theorem. It lies in NP, since a satisfying assignment is a certificate that can be checked in polynomial time.

Non-example: the halting problem is NP-hard but not NP-complete. It fails clause 1, since it is undecidable and every language in NP is decidable.

To show that a language $C$ in NP is NP-complete, it is enough to give $B \le_p C$ for one known NP-complete $B$ , since $\le_p$ is transitive. If some NP-complete language lies in P, then $\mathrm{P} = \mathrm{NP}$ .

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Formal language concept
NP concept
NP-hardness concept
P concept
Polynomial-time reduction concept
NP-completeness definition

Tag	`REKDJ8V504`
URI	`m2://REKDJ8V504`
Kind	definition
Writing	W0 stub
MSC	68Q17, 68Q15
Defines	NP-completeness
Uses	NP, NP-hardness, Polynomial-time reduction, Formal language, P
Changed	3 November 2026

NP-completeness

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here