Polynomial Reduction
多项式归约将问题 A 在多项式时间内转换为问题 B，若 B 可解则 A 可解，用于证明 NP-hard。
用途
证明问题难度与传递可解性，复杂度理论核心工具。
机制
A ≤_p B：存在多项式时间函数 f 将 A 实例映射到 B 实例，使 A(x)=B(f(x))。若 B∈P 则 A∈P。若已知 A 为 NP-hard 且 A≤_p B 则 B 为 NP-hard。
用例
- 复杂度证明
- NP-hard 归约
- 问题分类
多项式归约将问题 A 在多项式时间内转换为问题 B，若 B 可解则 A 可解，用于证明 NP-hard。
证明问题难度与传递可解性，复杂度理论核心工具。
A ≤_p B：存在多项式时间函数 f 将 A 实例映射到 B 实例，使 A(x)=B(f(x))。若 B∈P 则 A∈P。若已知 A 为 NP-hard 且 A≤_p B 则 B 为 NP-hard。