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

{{unreferenced|time=2011-10-17T01:57:19+00:00}}
{{NoteTA
|G1 = IT
}}
在[[计算理论]]领域中，若一个数值[[算法]]的[[时间复杂度]]可以表示为输入数值N的[[多项式]]，则称其时间复杂度为'''伪多项式时间'''。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的[[指数时间|幂]]。

一个具有伪多项式时间复杂度的[[NP完全|NP完全问题]]称之为{{le|弱NP完全|Weak NP-completeness|弱NP完全问题}}，而在[[P/NP问题|P!=NP]]的情况下，若一个NP完全问题被证明没有伪[[多项式时间归约|多项式时间]]复杂度的解，则称之为{{le|强NP完全|Strong NP-completeness|强NP完全问题}}。

== 例子 ==
在[[質數測試|-{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>。因此，上述算法是一个伪多项式时间算法。

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

[[Category:理论计算机科学]]
[[Category:计算复杂性理论]]
[[Category:复杂度类]]
[[Category:算法分析]]