伪多项式时间 在计算理论领域中若一个数值算法的时间复杂度可以表示为输入数值N的多项式则称其时间复杂度为伪多项式时间这是由于N的值是N的位数的幂故该算法的时间复杂度实际上应视为输入数值N的位数的幂 一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题英语Weak NPcompleteness而在PNP的情况下若一个NP完全问题被证明没有伪多项式时间复杂度的解则称之为强NP完全问题英语Strong NPcompleteness