伪多项式时间

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

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

例子

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

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