# Many-one reduction

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A≤mB means a total computable map f satisfies x∈A exactly when f(x)∈B for every x.

mko-many-one-reduction · definition · v0.10.0



## Mathematical statement

Finite families declare complete source and target carriers, both decision predicates and an aligned mapping table. Qualify totality, then check both directions of membership equivalence for every x; yes-only checks are insufficient. Composition preserves direction: A≤mB and B≤mC give A≤mC. If A≤mB and B is decidable, compute f then run the B decider to decide A; the reverse implication is not supplied. Partial maps, reversed transfer and conflation with Turing reduction must be rejected. A finite table certifies only its declared finite domain; an infinite domain still needs a complete computable algorithm and termination argument.





## Representative formula (exact TeX)

R(A,B,f)=1





## Assumptions


- Exact families use declared bounded finite carriers and complete mapping arrays.
- Decider transfer uses complete finite truth tables or an explicitly total terminating computation.





## Symbol scope


- R — many-one-reduction predicate
- A — source decision problem
- B — target decision problem
- f — total computable map





## Intuition, definition, and misconceptions

Total-map qualification precedes reduction status.

Membership equivalence requires both yes and no directions.

Composition and decider transfer both preserve direction.

Yes-only checks or a partial map do not certify a reduction, and decidability of A does not transfer backwards to B.





## Adopted derivation guide

[A complete finite reduction with preserved direction](https://ocme.evemisslab.com/en/derivations/derivation-mko-many-one-reduction-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Decision problem](https://ocme.evemisslab.com/en/mko/mko-decision-problem/) — Use yes/no predicates.
- [Function mapping](https://ocme.evemisslab.com/en/mko/mko-function-mapping/) — Require a complete total map.
- [Function composition](https://ocme.evemisslab.com/en/mko/mko-composition/) — Compose reductions in order.
- [Turing-machine decision model](https://ocme.evemisslab.com/en/mko/mko-turing-machine-decision-model/) — Keep decider and termination boundaries explicit.





## Verification boundary

Finite tables do not prove infinite-domain computability and are not Turing reductions.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add undecidability reductions and recognizability boundaries.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/many-one-reduction.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-many-one-reduction/index.md)