Atlas of Fundamental Concepts

© 2026 Advay Mengle Β· Terms Β· Edit me!

Graph centered on Many-one reduction, showing the selected concept and its surrounding relations.Preparing the interactive atlas…
Curated starting points

Stories & Views

Open the stories and views directory
Relationship-aware analysis

Compare concepts

Choose two concepts to compare or connect.
Reading the graph

Guide to the Atlas

Open full user guide

Canonical static concept record

Many-one reduction

Open this concept in the interactive graphRead the Markdown equivalent

Summary

A total computable function ff reducing a set or decision problem AA to BB by preserving membership exactly: x∈Ax\in A if and only if f(x)∈Bf(x)\in B.

Record metadata

Canonical name
Many-one reduction
Concept ID
many_one_reduction
Content version
2.3.0
Primary field
Mathematics
Fields
Mathematics
Primary domain
Computability theory
Domains
Computability theory
Alternate terminology
No alternate terminology is currently authored for this record.
Concept type
Computable reduction

Concept sources

Incoming relations (arrows to this concept)

Each relation below ends at this concept.

Computable functionMany-one reduction

Permalink to relation

This is an authored directed relation from the source endpoint to the target endpoint.

Relation ID
computability_function_to_many_one_reduction
Relation type
Mathematical formulation mathematical-formulation
Direction
source β†’ target
Endpoint roles
source: Mathematically formulates; target: Mathematically formulated using
Authored annotation
membership-preserving translator

Authored explanation

The reduction is the computable map ff whose membership-preservation equivalence transfers decidability and many undecidability arguments from the target problem to the source problem.

How to interpret this relation type

A mathematical concept supplies part of the formal language, state space, representation, or analytic machinery used by a scientific or mathematical-physics concept. The source is the mathematical predecessor; this does not claim that physical content follows from mathematics alone.

Relation sources

Decision problemMany-one reduction

Permalink to relation

This is an authored directed relation from the source endpoint to the target endpoint.

Relation ID
computability_decision_problem_to_many_one_reduction
Relation type
Add data add-data
Direction
source β†’ target
Endpoint roles
source: Builds toward; target: Built from
Authored annotation
encode instances computably

Authored explanation

A many-one reduction supplies a total computable translation of instances so that one answer to the target decision problem decides the original instance without adaptive oracle queries.

How to interpret this relation type

Equip an existing carrier or structured object with additional chosen data, when such compatible data exists. Use a construction junction when several independently meaningful inputs must coexist on the same carrier or interact compatibly.

Relation sources

Outgoing relations (arrows from this concept)

Each relation below starts at this concept.

No direct relations are authored in this direction.