多项式时间归约 - 维基百科，自由的百科全书

此條目可参照英語維基百科相應條目来扩充。 (2022年8月11日) 若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

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

1. ^ ^{1.0 1.1} Kleinberg, Jon; Tardos, Éva. Algorithm Design. Pearson Education. 2006: 452–453. ISBN 978-0-321-37291-8. 
2. ^ Mandal, Debasis; Pavan, A.; Venugopalan, Rajeswari. Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science. 2014 [2022-08-11]. ISBN 978-3-939897-77-4. （原始内容存档于2022-06-17）. 
3. ^ Wegener, Ingo, Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer: 60, 2005, ISBN 9783540274773 .
4. ^ ^{4.0 4.1} Goldreich, Oded, Computational Complexity: A Conceptual Perspective, Cambridge University Press: 59–60, 2008, ISBN 9781139472746 
5. ^ 黄文奇; 陈志祥. 递归集的k-1-度上半格的不可补性与不可分配性. 数学学报. 1989-08-29, (04): 517-524 [2022-08-11]. ISSN 0583-1431. （原始内容存档于2022-08-11） （中文（中国大陆））. 
6. ^ Buss, S.R.; Hay, L., On truth-table reducibility to SAT and the difference hierarchy over NP, Proceedings of Third Annual Structure in Complexity Theory Conference: 224–233, 1988, CiteSeerX 10.1.1.5.2387 , ISBN 978-0-8186-0866-7, doi:10.1109/SCT.1988.5282 .