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

以互动方式浏览历史

←上一版本下一版本→

删除的内容添加的内容

可视化wikitext

行内

2014年12月8日 (一) 10:31的版本

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

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

例子

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

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

@@ 第5行： / 第5行： @@
 == 例子 ==
-在[[素性测试]]中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数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)</math>。因此，上述算法是一个伪多项式时间算法。
+在[[素性测试]]中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数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>。因此，上述算法是一个伪多项式时间算法。
 其它被证明只具有伪多项式时间算法解的问题有[[背包问题]]，[[子集合加总问题]]。