什麼是偽多項式時間演算法？

01-29

Stack Overflow上有人關於這個概念(Pseudo-polynomial time)進行過詳細解釋。

原答案：

algorithm - What is pseudopolynomial time? How does it differ from polynomial time?

我大概翻譯一下：

想要理解「偽多項式時間」，我們需要先給出「多項式時間」的一個清楚的定義。
對於「多項式時間」，我們的直觀概念是時間複雜度 $O(n^{k} )$ ,其中 $k$ 是一常數。比如，選擇排序的時間複雜度是 $O(n^{2} )$ ，是多項式時間；暴力解決TSP問題的時間複雜度是 $O(ncdot n!)$ ，不是多項式時間。我們稱這種時間複雜度為「傳統時間複雜度」。
我們通常認為傳統時間複雜度中的變數 $n$ 表示數據的輸入規模。比如，選擇排序中， $n$ 指待排序數組中元素的個數；TSP問題中 $n$ 表示圖中節點的數量。但是，這些所謂的輸入規模，僅僅是直觀的定義，並不足夠嚴謹。為了標準化這些 $n$ ，在計算標準時間複雜度時，我們給出了輸入規模的標準定義：
一個問題的輸入規模是保存輸入數據所需要的bit位數。
比如，如果排序演算法的輸入是一個32-bit整數數組，那麼輸入規模就是 $32n$ ， $n$ 是指數組中元素的個數。對於一個帶有 $n$ 個節點、 $m$ 條邊的圖，需要的bit位數就是 $Omega (n+m)$ 。
了解了輸入規模的定義，我們來看「多項式時間」的標準定義：
對於一個問題，在輸入規模為x的情況下，如果一個演算法能夠在O( $x^{k}$ )時間內解決此問題，則我們稱此演算法是多項式時間的，其中 $k$ 為一常數。
當我們處理一些圖論、鏈表、數組、樹等問題時，這個標準定義下的多項式時間和我們傳統的多項式時間相差無幾。比如，用選擇排序對元素個數為 $n$ 的數組進行排序時，傳統時間複雜度為 $O(n^{2} )$ 。輸入規模 $x=32n$ ，因此，得到的標準時間複雜度是 $O(x^{2} )$ ，仍然是多項式時間。

類似的，假設在帶有 $n$ 個節點、 $m$ 條邊的圖中做DFS(深度優先搜索)，傳統時間複雜度為 $O(n+m)$ 。數據規模 $x=Omega (n+m)$ ，因此，標準時間複雜度是 $O(x )$ ，仍是多項式時間的。
然而，當我們處理一些與數論有關的問題時，事情就不太樂觀了。現在我們來討論判斷一個整數是否為素數的演算法，下面是一個簡單的演算法：
function isPrime(n): for i from 2 to n - 1: if (n mod i) = 0, return false return true
顯然，這個演算法在傳統時間複雜度計算方法中是多項式時間的。我們不妨認為它的傳統時間複雜度是 $O(n^{4} )$ 。然後我們再來分析這個問題的輸入規模，可能有的同學會說，對於32-bit整數，這個輸入規模不就是32嗎？這話雖然沒錯，但是因為在這個問題中，輸入規模完全依賴於 $n$ 的大小，所以 $n$ 的範圍不再限制在32-bit整數的範圍內，而是要探討當 $n$ 更大時對數據規模的影響。我們知道，保存一個整數所需要的bit位數 $x=logn$ ，因此，在標準的時間複雜度中，此演算法的複雜度變為了 $O(2^{4x} )$ !這已經不再是多項式時間，而是一個指數時間。
我們可以從下面這個例子中直觀感受一下這種指數時間的增長速度：
對於一個二進位串：
10001010101011
我們記指數時間複雜度演算法運行時間為T。
然後，我們在二進位串後面僅僅增加一位：
100010101010111
這時，演算法運行時間會變為2T(至少)！因此，我們僅僅增加幾個bit 就會使得演算法運行時間成倍成倍的增長。

... ...
最後我們來說偽多項式時間的定義：
如果一個演算法的傳統時間複雜度是多項式時間的，而標準時間複雜度不是多項式時間的，則我們稱這個演算法是偽多項式時間的。

除此之外，原回答者還提到了偽多項式時間演算法在加密中的應用，多項式時間的素數判斷演算法等，有興趣的同學請移步原答案。

希望對問題有所幫助。

演算法的時間複雜度是輸入數據的多項式表達，但卻是輸入數據長度的指數時間表達

剛剛在看一個強NP完全的歸結問題，呵呵來回答一下。所謂的偽多項式時間演算法, 是NPC問題的一種, 存在複雜度是關於實例規模和實例所有參數中絕對值最大數是成多項式關係的演算法, 這樣的演算法稱為偽多項式時間演算法, 這樣的問題是NPC中較簡單的問題。如果一個NPC問題存在偽多項式時間演算法，那麼稱其為Weakly NP-Complete。否則，稱為Strongly NP-Complete.

經典一點的偽多項式時間演算法有背包問題，一個數是否是素數問題。因為這個多項式不是input size的多項式：背包大小是N,但是input size是log(N)；素數判別問題，判定一個數N，要進行sqrt(N)次，是這個數的多項式時間，但是對這個數的長度來說是指數的，比如吧N寫成二進位，D位數，要進行整除的次數是O(2^D)次的。

多項式時間演算法 (polynomial time algorithm) 表示：演算法的複雜度與輸入的規模呈多項式關係。

偽多項式時間演算法 (pseudopolynomial time algorithm) 是表示：演算法的複雜度與輸入規模呈指數關係，與輸入的數值大小呈多項式關係。

舉兩個對比的例子：

冒泡排序：給定 n 個64位的數字，進行 n-1 次掃描交換，將數字從小到大排序。

素數測試：給定數字 n，通過從 2 到根號 n 的整數遍歷，判斷 n 是否為素數。

字面上看，兩者複雜度都是 O(n^k) ( k 為整數) 。但區別在於，前者的 n 是數字個數的多少，後者的 n 是數字的大小。

因此，前者輸入總規模 s1 增長與數字大小無關，s1 = 64n；後者增長規模與數字大小緊密相關，輸入總規模為 s2 = logn 。

所以可知冒泡排序中複雜度 O(n^2) = O(s1^2/64^2) 為多項式演算法，後者素數測試O(n) = O(2^(s2)) 為偽多項式演算法啦。

如有錯誤，歡迎一起討論~

演算法複雜度中的n的大小是輸入在二進位表示下的長度。而偽多項式是指運行次數是關於輸入的一進位長度的多項式