跳转到内容

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

维基百科,自由的百科全书
删除的内容 添加的内容
Tang891228留言 | 贡献
纠正错误
第3行: 第3行:
|G1 = IT
|G1 = IT
}}
}}
在[[计算理论]]领域中,若一个数值[[算法]]的[[时间复杂度]]可以表示为输入数值规模N的[[多项式]],但其运行时间与输入数值规模N的二进制位数呈指数增长关系,则称其时间复杂度为'''伪多项式时间'''。这是由于,N的值是N的位数的幂,故该算法的时间复杂度实际上应视为输入数值N的位数的[[指数时间|幂]]。
在[[计算理论]]领域中,若一个数值[[算法]]的[[时间复杂度]]可以表示为输入数值N的[[多项式]],则称其时间复杂度为'''伪多项式时间'''。这是由于,N的值是N的位数的幂,故该算法的时间复杂度实际上应视为输入数值N的位数的[[指数时间|幂]]。


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

2019年8月2日 (五) 10:47的版本

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

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

例子

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

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