Complete (complexity)¶

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8594
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Computational Complexity Theory → Computer Science & Software Engineering

Core Idea¶

Complete (complexity) is treated here as the recurring computing and information systems identity summarized by this source-grounded definition: In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.

How would you explain it like I'm…

The Master Puzzle

Imagine a big box of puzzles, and one special puzzle in the box has a trick: every other puzzle in the box can be changed into it. So if you could solve that special one, you could solve them all. That special puzzle is called complete for that box.

Hardest Problem in the Group

Computer scientists sort problems into groups, called complexity classes, depending on how much work they take to solve. A problem is complete for a group if it is in the group and every other problem in the group can be changed into it, using an allowed kind of changing trick called a reduction. That means if you had a fast way to solve the complete problem, you could use it to solve all the others too. So the complete problems are, in a special sense, the hardest ones in the group. The most famous example is the NP-complete problems, which include many hard problems people face in real life.

Complete for a Complexity Class

In computational complexity theory, a complexity class is a set of problems that can be solved within some resource limit. A problem p is hard for a class C if every problem in C can be reduced to p — converted into an instance of p — using a specified type of reduction. If p is both hard for C and itself a member of C, it is complete for C, or 'C-complete'. Being complete makes p among the 'hardest' or 'most expressive' problems in C, in a technical sense: solving p lets you solve anything in C through the reduction. It doesn't just mean the problem takes a long time — it's about every problem in the class translating into it. NP-complete was the first such class defined and is the best known; a problem that is hard for C but not necessarily in C is called C-hard.

Completeness in complexity theory formalizes the idea of a hardest, or most expressive, problem in a complexity class. It is defined relative to a type of reduction, a transformation that maps instances of one problem to instances of another. A problem p is hard for class C (C-hard) under a given reduction type if every problem in C reduces to p by that type of reduction. If p is C-hard and also belongs to C, it is C-complete, and the set of all such problems is itself denoted C-complete. The reduction type matters: completeness is always completeness for a class under a specified kind of reduction. NP-complete was the first complete class defined and is the best known, containing many hard problems arising in practice.

Scope of Application¶

Documented setting. The first complete class to be defined and the most well known is NP-complete, a class that contains many difficult-to-solve problems that arise in practice.
Documented setting. In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.
Documented setting. More formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction (of the given type) from any problem.
Documented setting. If a problem is both hard for the class and a member of the class, it is complete for that class (for that type of reduction).
Documented setting. A problem that is complete for a class C is said to be C-complete, and the class of all problems complete for C is denoted C-complete.

Clarity¶

A clear use of Complete (complexity) names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.

Manages Complexity¶

Complete (complexity) compresses multiple computing and information systems details into a stable diagnostic relation. The source shows both the central mechanism—more formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction (of the given type) from any problem in C to p.—and the practical consequence—similarly, a problem hard for a class C is called.

Abstract Reasoning¶

Type the carrier. Identify the computing and information systems entities to which the claim applies.
State the relation. Use the source-grounded identity: In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.
Check operation and conditions. If a problem is both hard for the class and a member of the class, it is complete for that class (for that type of reduction). 4.

Knowledge Transfer¶

Within the home domain. Knowledge about Complete (complexity) transfers literally when a new case preserves the same carrier type, relation, and recognition test. The first complete class to be defined and the most well known is NP-complete, a class that contains many difficult-to-solve problems that arise in practice. In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity.

Relationships to Other Abstractions¶

Current abstraction Complete (complexity) Domain-specific

Parents (1) — more general patterns this builds on

Complete (complexity) presupposes Complexity Class Domain-specific

Completeness is defined relative to membership in a complexity class and reductions from every class member.

Neighborhood in Abstraction Space¶

Complete (complexity) sits in a moderately populated region (58^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Computation Models & Complexity Classes (37 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08