可归约性

定义

归约性(reduction)：将一个问题转化为另一个问题，且使得第二个问题的答案能够用于解决第一个问题

映射可归约性

可归约性的形式化定义有多种表达方式，其中一种是映射可归约性(mapping reducibility)。“用映射可归约性将问题 A 归约为问题 B”意思是：存在一个可计算函数，它将问题 A 的实例转化为 B 的实例。简记为：$A{\le }_{m}B$

$$\exists f:{\Sigma }^{\ast }\to {\Sigma }^{\ast },\forall (w\in A)\iff f(w)\in B$$

笔记

这个可计算函数就叫做 $A$ 到 $B$ 的归约

图灵可归约性

这是映射可归约性的一个扩展，取消了可计算函数这么一个概念。而是直接在图灵机的计算过程中假设问题 A 可以通过某种神秘的方式判定，然后再来判断问题 B 是否可以判定了。

如果在问题 A 能够判定的条件下，问题 B 也能够判定；问题 A 不能判定的条件下，问题 B 也不能够判定，那么我们就说”问题 B 相对于问题 A 是可判定的”。同时，也称”问题 B 图灵可归约到问题 A”，记作 $A{\le }_{T}B$

意义

归约性给出了一些看似不同的问题之间的内在一致性。