此条目没有列出任何参考或来源. (2011年10月17日)
维基百科所有的内容都应该可供查证.请协助补充可靠来源以改善这篇条目.无法查证的内容可能会因为异议提出而移除.
在计算理论领域中,若一个数值算法的时间复杂度可以表示为输入数值N的多项式,则称其时间复杂度为伪多项式时间.这是由于,N的值是N的位数的幂,故该算法的时间复杂度实际上应视为输入数值N的位数的幂.
一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题,而在P!=NP的情况下,若一个NP完全问题被证明没有伪多项式时间复杂度的解,则称之为强NP完全问题.
其它被证明只具有伪多项式时间算法解的问题有背包问题,子集合加总问题.
本页面最后修订于2021年4月30日 (星期五) 06:00.