多项式时间归约

在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法。如果将第一个问题转换成第二个的时间，且子程序被调用的次数都是多项式级别的，那么第一个问题可以多项式时间规约到第二个问题。^[1]

多项式时间规约证明了第一个问题不比第二个问题难。因为当第二个问题存在高效率算法时，第一个也存在。因为逆否命题，如果第一个问题没有高效率算法时，第二个也没有。^[1]计算复杂性理论中经常使用多项式时间规约来定义复杂性类和完全问题。

规约的类型

多项式时间归约有几种不同类型，取决于具体如何使用子程序。

三种最常见的多项式时间规约类型，从最多限制到最少限制的，是多项式时间多一规约（英语：Many-one reduction），真值表规约（英语：Truth-table reductions），图灵规约。^[2]最常用的是多一规约，在某些情况下短语“多项式时间规约”可能仅指多项式时间多一规约。^[3]

多一规约

从问题A到问题B（两个通常都需要是决定性问题）的多项式时间多一规约（英语：Many-one reduction），是将问题A的输入转换成问题B的输入的多项式算法，使得转换后的问题与原问题有相同的输出。问题A的实例x，可以通过此转换为问题B的实例y，将y输入解决问题B的算法，然后返回它的输出。多项式时间多一规约也被称为Karp规约，以理查德·卡普命名。这种类型的规约被表示为${\displaystyle A\leq _{m}^{P}B}$或${\displaystyle A\leq _{p}B}$。^[4][5]

真值表归约

从问题A到问题B（两个都是决定性问题）的多项式时间真值表规约（英语：Truth-table reductions），是将问题A的输入转换成固定数量个问题B的输入的多项式算法，使得原问题的输出可以被表示为问题B输出的函数。将 B 的输出映射到 A 的输出的函数对于所有输入必须相同，所以它可以用真值表表示。 这种类型的归约可以用表达式${\displaystyle A\leq _{tt}^{P}B}$来表示。^[6]

图灵规约

从问题 A 到问题 B 的多项式时间图灵规约是一种算法，它需要调用问题 B 的子程序多项式次，以及这些子程序调用之外的多项式时间来解决问题 A。 多项式时间图灵规约也称为库克规约，以史蒂芬·库克命名。 这种类型的归约可以用表达式${\displaystyle A\leq _{T}^{P}B}$来表示。^[4]多一归约可以被视为图灵归约的受限变体，其中对问题 B 的子程序的调用次数恰好为 1，且归约返回的值与子程序返回的值相同。