在計算復(fù)雜性里面，如果一個算法的時間復(fù)雜度是輸入數(shù)據(jù)的多項式表達(dá)，但卻是輸入長度的指數(shù)時間算法，那么稱其為偽多項式時間。
如果一個NPC問題存在偽多項式時間算法，那么稱其為Weakly NP-Complete。否則，稱為Strongly NP-Complete.
很明顯的一個例子是0-1背包問題，這一點經(jīng)常容易引起別人的誤解。其實0-1背包問題是一個NPC問題，你可以簡單的把它規(guī)約到子集和問題，但是有人經(jīng)常爭辯說0-1 kanpsack問題存在Polynomial Algorithm，那么問題就在這里，那個所謂的Polynomial Algorithm is Pseudo-Polynomial actually！
一個經(jīng)典0-1背包問題的DP解法的時間復(fù)雜度是O(nW)，W為背包容量，但是背包容量是否需要枚舉[min(…),\sum(…)]呢？所以問題就在這里了復(fù)雜度是O(n2^n)…
還有一個問題就是素性檢測！這個當(dāng)然也是NPC的了。。
In the case of primality, it turns out there is a different algorithm for testing whether n is prime (discovered in 2002) which runs in time O(log6n).
如果仍然不是很清楚，那么需要熟悉一下NPC與P類問題區(qū)別，下面是一個不錯的表格。。。
不過貌似在源blog中有一處錯誤。。。Linear Programming的確是P問題，但是解決這個P問題的simplex 算法卻不是Polynomial的，這個需要注意！