归约维基百科,自由的 encyclopedia 在可计算性理论与计算复杂性理论中,所谓的归约是将某个计算问题(英语:computational problem)变换为另一个问题的过程。可用归约法定义某些问题的复杂度类(因变换过程而异)。 Example of a reduction from the boolean satisfiability problem (A ∨ B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ C) to a vertex cover problem. The blue vertices form a minimum vertex cover, and the blue vertices in the gray oval correspond to a satisfying truth assignment for the original formula. 以直觉观之,如果存在能有效解决问题B的算法,也可以作为解决问题A的子程序,则将问题A称为“可归约”到问题B,因此求解A并不会比求解B更困难。 一般写作A ≤m B,通常也在≤符号下标使用的归约类型(m:映射缩小,p:多项式缩减)。 将一组问题归约到特定类型所产生的数学结构,通常形成预序关系,其等价类可用于定义求解难度和复杂度。
在可计算性理论与计算复杂性理论中,所谓的归约是将某个计算问题(英语:computational problem)变换为另一个问题的过程。可用归约法定义某些问题的复杂度类(因变换过程而异)。 Example of a reduction from the boolean satisfiability problem (A ∨ B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ C) to a vertex cover problem. The blue vertices form a minimum vertex cover, and the blue vertices in the gray oval correspond to a satisfying truth assignment for the original formula. 以直觉观之,如果存在能有效解决问题B的算法,也可以作为解决问题A的子程序,则将问题A称为“可归约”到问题B,因此求解A并不会比求解B更困难。 一般写作A ≤m B,通常也在≤符号下标使用的归约类型(m:映射缩小,p:多项式缩减)。 将一组问题归约到特定类型所产生的数学结构,通常形成预序关系,其等价类可用于定义求解难度和复杂度。