查看“︁多项式时间归约”︁的源代码

{{expand english|time=2022-08-11}}
{{noteTA
|G1=IT
}}
在[[計算複雜性理論|计算复杂性理论]]中，'''多项式时间归约'''是指假设已有解决一个问题的[[子程序]]，利用它在[[时间复杂度|多项式时间]]内（不考虑子程序运行所用时间）解决另一个问题的[[归约]]方法。如果将第一个问题转换成第二个的时间，且子程序被调用的次数都是多项式级别的，那么第一个问题可以多项式时间规约到第二个问题。<ref name=":0">{{cite book|last1=Kleinberg|first1=Jon|authorlink1=Jon Kleinberg|last2=Tardos|first2=Éva|authorlink2=Éva Tardos|year=2006|publisher=Pearson Education|title=Algorithm Design|isbn=978-0-321-37291-8|pages=452–453}}</ref>

多项式时间规约证明了第一个问题不比第二个问题难。因为当第二个问题存在高效率[[算法]]时，第一个也存在。因为[[逆否命题]]，如果第一个问题没有高效率算法时，第二个也没有。<ref name=":0" />计算复杂性理论中经常使用多项式时间规约来定义[[复杂性类]]和[[完備 (複雜度)|完全问题]]。

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

三种最常见的多项式时间规约类型，从最多限制到最少限制的，是多项式时间{{En-link|多一规约|Many-one reduction}}，{{En-link|真值表规约|Truth-table reductions}}，[[圖靈歸約|图灵规约]]。<ref>{{cite conference |last1=Mandal |first1=Debasis |last2=Pavan |first2=A. |last3=Venugopalan |first3=Rajeswari |year=2014 |title=Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis |url=http://drops.dagstuhl.de/opus/volltexte/2014/4862/ |conference=34th International Conference on Foundation of Software Technology and Theoretical Computer Science |isbn=978-3-939897-77-4 |access-date=2022-08-11 |archive-date=2022-06-17 |archive-url=https://web.archive.org/web/20220617073453/https://drops.dagstuhl.de/opus/volltexte/2014/4862/ |dead-url=no }}</ref>最常用的是多一规约，在某些情况下短语“多项式时间规约”可能仅指多项式时间多一规约。<ref>{{citation|title=Complexity Theory: Exploring the Limits of Efficient Algorithms|first=Ingo|last=Wegener|authorlink=Ingo Wegener|page=60|publisher=Springer|year=2005|isbn=9783540274773}}.</ref>

=== 多一规约 ===
从问题A到问题B（两个通常都需要是[[決定性問題|决定性问题]]）的多项式时间{{En-link|多一规约|Many-one reduction}}，是将问题A的输入转换成问题B的输入的多项式算法，使得转换后的问题与原问题有相同的输出。问题A的实例x，可以通过此转换為问题B的实例y，将y输入解决问题B的算法，然后返回它的输出。多项式时间多一规约也被称为'''Karp规约'''，以[[理查德·卡普]]命名。这种类型的规约被表示为<math>A \le_m^P B</math>或<math>A \le_p B</math>。<ref name=":1">{{citation|title=Computational Complexity: A Conceptual Perspective|first=Oded|last=Goldreich|authorlink=Oded Goldreich|publisher=Cambridge University Press|year=2008|isbn=9781139472746|pages=59–60}}</ref><ref>{{Cite journal |author=黄文奇 |author2=陈志祥 |date=1989-08-29 |title=递归集的k-1-度上半格的不可补性与不可分配性 |url=https://kns.cnki.net/kcms/detail/detail.aspx?filename=SXXB198904010&dbcode=CJFD&dbname=CJFD1989&v=X8ksT7IkMdbWbHxnrsZMrd7uwG9kED3TC6t7y2MJG6podIGRotPBVTEJI1INw9GH |journal=数学学报 |language=zh-cn |issue=04 |page=517-524 |issn=0583-1431 |access-date=2022-08-11 |archive-date=2022-08-11 |archive-url=https://web.archive.org/web/20220811153904/https://kns.cnki.net/kcms/detail/detail.aspx?filename=SXXB198904010&dbcode=CJFD&dbname=CJFD1989&v=X8ksT7IkMdbWbHxnrsZMrd7uwG9kED3TC6t7y2MJG6podIGRotPBVTEJI1INw9GH |dead-url=no }}</ref>

=== 真值表归约 ===
从问题A到问题B（两个都是[[決定性問題|决定性问题]]）的多项式时间{{En-link|真值表规约|Truth-table reductions}}，是将问题A的输入转换成固定数量个问题B的输入的多项式算法，使得原问题的输出可以被表示为问题B输出的函数。将 B 的输出映射到 A 的输出的函数对于所有输入必须相同，所以它可以用[[真值表]]表示。 这种类型的归约可以用表达式<math>A\leq_{tt}^{P}B</math>来表示。<ref>{{citation|last1=Buss|first1=S.R.|author1-link=Samuel Buss|last2=Hay|first2=L.|contribution=On truth-table reducibility to SAT and the difference hierarchy over NP|doi=10.1109/SCT.1988.5282|pages=224–233|title=Proceedings of Third Annual Structure in Complexity Theory Conference|year=1988|isbn=978-0-8186-0866-7|citeseerx=10.1.1.5.2387}}.</ref>

=== 图灵规约 ===
从问题 A 到问题 B 的多项式时间[[圖靈歸約|图灵规约]]是一种[[算法]]，它需要调用问题 B 的子程序多项式次，以及这些子程序调用之外的多项式时间来解决问题 A。 多项式时间图灵规约也称为'''库克规约'''，以[[史蒂芬·库克]]命名。 这种类型的归约可以用表达式<math>A \le_T^P B</math>来表示。<ref name=":1" />多一归约可以被视为图灵归约的受限变体，其中对问题 B 的子程序的调用次数恰好为 1，且归约返回的值与子程序返回的值相同。

== 参考文献 ==
<references />

{{Authority control}}
[[Category:歸約]]