伪多项式时间：修订间差异

删除的内容添加的内容

行内

2023年4月8日 (六) 09:28的最新版本

在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。

一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题（英语：Weak NP-completeness），而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为强NP完全问题（英语：Strong NP-completeness）。

例子

在素性测试中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数N，使用从最小的素数2开始，到 ${\sqrt {N}}$ 为止的整数依次对N进行试除，如果均无法整除N，则N是素数，这个过程需要进行至多约 ${\sqrt {N}}$ 次整数除法，即其时间复杂度为 $O({\sqrt {N}})$ ，为N的多项式。令D为N的二进制表示的位数，那么N可以表示为以2为底D的幂，因此素性测试问题的时间复杂度用D表示应为 $O(2^{D/2})$ 。因此，上述算法是一个伪多项式时间算法。

其它被证明只具有伪多项式时间算法解的问题有背包问题，子集合加总问题。

@@ 第3行： / 第3行： @@
 |G1 = IT
 }}
-在[[计算理论]]领域中，若一个数值[[算法]]的[[时间复杂度]]可以表示为输入数值规模N的[[多项式]]，但其运行时间与输入数值规模N的二进制位数呈指数增长关系，则称其时间复杂度为'''伪多项式时间'''。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的[[指数时间|幂]]。
+在[[计算理论]]领域中，若一个数值[[算法]]的[[时间复杂度]]可以表示为输入数值N的[[多项式]]，则称其时间复杂度为'''伪多项式时间'''。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的[[指数时间|幂]]。
-一个具有伪多项式时间复杂度的[[NP完全|NP完全问题]]称之为[[弱NP完全|弱NP完全问题]]，而在[[P/NP问题|P!=NP]]的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为[[强NP完全|强NP完全问题]]。
+一个具有伪多项式时间复杂度的[[NP完全|NP完全问题]]称之为{{le|弱NP完全|Weak NP-completeness|弱NP完全问题}}，而在[[P/NP问题|P!=NP]]的情况下，若一个NP完全问题被证明没有伪[[多项式时间归约|多项式时间]]复杂度的解，则称之为{{le|强NP完全|Strong NP-completeness|强NP完全问题}}。
 == 例子 ==
-在[[素性测试]]中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数N，使用从最小的[[素数]]2开始，到<math>\sqrt{N}</math>为止的整数依次对N进行试除，如果均无法整除N，则N是素数，这个过程需要进行至多约<math>\sqrt{N}</math>次整数除法，即其时间复杂度为<math>O(\sqrt{N})</math>，为N的多项式。令D为N的二进制表示的位数，那么N可以表示为以2为底D的[[幂]]，因此素性测试问题的时间复杂度用D表示应为<math>O(2^{D/2})</math>。因此，上述算法是一个伪多项式时间算法。
+在[[質數測試|-{zh-hant:質數測試;zh-hans:素性测试}-]]中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数N，使用从最小的[[質數|-{zh-hant:質數;zh-hans:素数}-]]2开始，到<math>\sqrt{N}</math>为止的整数依次对N进行试除，如果均无法整除N，则N是素数，这个过程需要进行至多约<math>\sqrt{N}</math>次整数除法，即其时间复杂度为<math>O(\sqrt{N})</math>，为N的多项式。令D为N的二进制表示的位数，那么N可以表示为以2为底D的[[幂]]，因此素性测试问题的时间复杂度用D表示应为<math>O(2^{D/2})</math>。因此，上述算法是一个伪多项式时间算法。
 其它被证明只具有伪多项式时间算法解的问题有[[背包问题]]，[[子集合加总问题]]。