# 多對一歸約

A≤mB表示存在total computable f，使每個x皆滿足x∈A恰當f(x)∈B。

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



## 數學敘述

有限題族明示source carrier、target carrier、decision predicates與完整total mapping table，逐x雙向驗x∈A iff f(x)∈B；只驗yes instances不足。composition須保留方向：A≤mB且B≤mC推出A≤mC。若A≤mB且B decidable，先算f再跑B decider可得A decider；反向transfer不成立。partial map、倒轉方向與Turing reduction混同均須拒絕。有限mapping table只證指定finite domain；無限domain仍需完整可計算算法及termination certificate。





## 代表公式（精確 TeX）

R(A,B,f)=1





## 成立條件


- 本輪exact families限明示bounded finite carriers與complete mapping arrays。
- decider transfer使用完整finite truth tables或明示total termination。





## 符號作用域


- R — 多對一歸約述詞
- A — 來源判定問題
- B — 目標判定問題
- f — 全可計算映射





## 直觀、定義與常見誤解

total map資格先於reduction。

membership equivalence需正反雙向。

composition與decider transfer都保持正確方向。

只驗yes instances、使用partial map，或由A decidable倒推出B decidable。





## 已採用的推導導讀

[完整有限reduction與方向保持](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-many-one-reduction-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [決定問題](https://ocme.evemisslab.com/zh-Hant/mko/mko-decision-problem/) — yes/no predicates。
- [函數映射](https://ocme.evemisslab.com/zh-Hant/mko/mko-function-mapping/) — complete total map。
- [函數合成](https://ocme.evemisslab.com/zh-Hant/mko/mko-composition/) — reduction transitivity。
- [Turing機判定模型](https://ocme.evemisslab.com/zh-Hant/mko/mko-turing-machine-decision-model/) — decider與termination界線。





## 驗證界線

finite table不證無限domain computability；不混同Turing reduction。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入undecidability reductions與recognizability boundaries。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/many-one-reduction.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-many-one-reduction/index.md)