图灵归约（Turing Reduction）

图灵归约（Turing Reduction）是可计算性理论中的一种归约方式，由图灵在神谕图灵机框架下引入。若存在一台以问题B为神谕的图灵机能判定问题A，就说A图灵可归约到B，记作A≤ᴛB，表示A的难度不超过B。

概述

直观上，图灵归约允许在求解A的过程中，任意多次地调用一个能瞬间回答B成员资格的黑盒。只要借助这个神谕就能算出A，A便可归约到B。它是最一般、最宽松的归约之一，涵盖了多一归约和真值表归约等更受限的形式。

核心特点

• 神谕调用：归约过程可多次、自适应地询问神谕B，后续问题可依赖此前答案。
• 宽松性：比多一归约更强，A≤ᴛB时A的补也自动归约到B。
• 可计算性传递：若B可判定且A≤ᴛB，则A也可判定。
• 定义图灵度：图灵归约的双向等价（A≤ᴛB且B≤ᴛA）将问题划分为图灵度。

核心原理

图灵归约与多一归约的关键区别在于：多一归约只能把A的一个实例一次性变换成B的一个实例，而图灵归约可反复询问、并根据答案决定后续行为，甚至利用B的否定信息。正因如此，在复杂度理论中区分强弱不同的归约十分重要——NP完全性通常采用较严格的多项式时间多一归约，以免过度宽松的归约模糊了类之间的界限。

应用场景

图灵归约用于证明问题的不可判定性（把已知不可解问题归约到目标问题）、构造与比较图灵度、研究算术层级，以及在复杂度理论中定义多项式时间图灵归约（库克归约）以刻画搜索与判定问题的相对难度。

常见问题

问：图灵归约和多一归约有何不同？答：多一归约只做一次输入变换，图灵归约则可把B当作可反复调用的子程序，并依据回答自适应地继续计算，因此更为宽松通用。

问：为什么NP完全性不用图灵归约？答：因为图灵归约过于宽松，可能抹平NP与co-NP等类的差异，故通常采用更严格的多项式时间多一归约来定义完全性，以保持结论的精确性。