Reduction (complexity)
Transforming one problem into another to transfer solvability or hardness, the core tool of complexity theory.
At a glance
Key signals
0% cross fields · reaches 0 more
- Computer Science
- Computational Complexity
- Theory of Computation
- Explanation
- Examples
- Misconception
- Sourced relations
- Attribution
Dependencies
What this concept builds on and what it makes possible — derived from the atlas’s dependency, causal and structural relations, not from every related edge.
Enables · leads to
NP-completenessdepends onReduction (complexity)Established
NP-Completeness depends on Reduction.
System context
Polynomial-Time Reductionis aReduction (complexity)Established
Open Polynomial-Time Reduction →
Polynomial-Time Reduction is a kind of Reduction.
Structural role & consequence
Interpreted from the current atlas graph — what the connections mean, not just how many there are.
Currently dark in the atlas: no key date stored · 3 of 3 of its relations lack claim-level evidence.
atlas representation · Describes the current Thinking OS representation, not the state of the world.
Structural neighbourhood: 2 → 7 → 17 concepts reachable within 3 hops.
structural · Structural reach — being reachable is not the same as being understood.
All 2 of its relationships stay within its own discipline — a field-specific concept in the current atlas.
structural · Structural graph analysis — not a claim of importance, causation or history.
cross-field
2 within-field, 0 cross-field
Strengths & constraints
Constraints
- Evidence coverage currently thin in the atlas — few of its relationships carry claim-level evidence. atlas representation
- No dated history stored — the atlas records no key date for this concept. atlas representation
Conditions
- Read structurally — most of its relationships carry no external evidence yet, so claims here are graph-derived. structural
Dependency radial
What this concept builds on (left) and what it makes possible (right) — derived from dependency and causal relations.
What builds on this
1 concept build on this directly, 1 in total, across 3 disciplines.
Structural downstream reach along dependency edges — not a claim of historical necessity.
Seen through each discipline
How this concept sits in each of its fields — derived from its real connections in the graph, not asserted.
Through this lens it connects to NP-completeness and NP-completeness.
Through this lens it connects to NP-completeness, NP-completeness and Polynomial-Time Reduction.
Reduction (complexity) through the Computational Complexity lens →
Through this lens it connects to NP-completeness and NP-completeness.
Reduction (complexity) through the Theory of Computation lens →
Related ideas to explore
Concepts that look related but are not yet connected here — candidates for a connection to reason about, not established links.
- Connects 2 other ideas across 3 disciplines.
- Most of its connections are of the “Kind & structure” kind.
Derived from the graph’s real structure — observations, not a score.