偽多項式時間

在計算理論領域中，若一個數值演算法的時間複雜度可以表示為輸入數值N的多項式，則稱其時間複雜度為偽多項式時間。這是由於，N的值是N的位數的冪，故該演算法的時間複雜度實際上應視為輸入數值N的位數的冪。

一個具有偽多項式時間複雜度的NP完全問題稱之為弱NP完全問題，而在P!=NP的情況下，若一個NP完全問題被證明沒有偽多項式時間複雜度的解，則稱之為強NP完全問題。

例子

在質數測試中，使用較小的整數逐個對被測試數進行試除的演算法被認為是一個偽多項式時間演算法。對於給定的整數N，使用從最小的質數2開始，到${\sqrt {N}}$為止的整數依次對N進行試除，如果均無法整除N，則N是素數，這個過程需要進行至多約${\sqrt {N}}$次整數除法，即其時間複雜度為$O({\sqrt {N}})$，為N的多項式。令D為N的二進位表示的位數，那麼N可以表示為以2為底D的冪，因此素性測試問題的時間複雜度用D表示應為$O(2^{D/2})$。因此，上述演算法是一個偽多項式時間演算法。

其它被證明只具有偽多項式時間演算法解的問題有背包問題，子集合加總問題。