在學習Mathematica元編程和研究NP問題的過程中，本文所討論的問題是一個很好的切入點。NP問題有多種類型，在密碼學中，非對稱密碼算法都是基于NP問題這類困難問題設計的，但各種困難問題之間的差別也很大，例如，當密鑰長度相同時，RSA算法就不如基于橢圓曲線的算法安全，這是因為基于橢圓曲線的離散對數問題看起來更加困難，盡管這兩個算法都是基于NP問題設計的，而RSA算法又有多種漏洞可以利用，使得其復雜度降低到了亞指數級，而基于橢圓曲線的算法至少也有指數級的復雜度。本文所介紹的算法可以幫助您探索某種NP問題蘊含在多項式內的潛在規律。

多項式是一種常見的數學對象，多項式系數（又稱組合數）是指多項式的n次方的展開式的各項系數，如下圖所示，這是一個3項式的3次方的展開式。

有多種算法可以計算多項式系數（組合數）之和，但本文要求解的問題是求這個展開式的各項系數的位數之和（十進制），這就不得不把每一項系數的位數都計算出來，對于上圖所示的多項式來說，因為展開式的每一項的系數都是一位十進制整數，所以位數之和是10，如下圖所示，可以簡單地用幾個函數在不到1毫秒的時間內計算出來。

在這個簡潔的問題中，蘊含了一個NP問題，由于所有NP問題都可以互相轉換，故不再贅述是哪一個NP問題，只需知道本文要求解的問題目前還沒有多項式級別的時間復雜度的求解算法，這也是NP（非確定性多項式）問題的含義。

若要求解7項式的30次方的多項式系數的位數之和（以下簡稱：位數之和），計算時間就來到了20秒，如下圖所示：

考慮到多項式的結構的對稱性，可以計算出系數相同的項的個數，再乘以對應的系數的位數，經過一系列計算就能在20毫秒內得到位數之和，比上圖所示的快了近1000倍。這種算法將本文的問題提煉成一個NP問題，復雜度取決于有多少種不同的系數，對于每一種不同的系數，算法只需要一次計算就能求解出這種系數的位數之和與帶有這種系數的項的個數。通過觀察多項式展開式的每一項的冪，易知，對于3項式的3次方的展開式的項來說，只有三種系數。

但這只不過是把階乘級的復雜度降低到指數級，而且這種算法的空間復雜度與其時間復雜度一樣高！非常消耗內存，因為要窮舉每一種系數。通過觀察多項式展開式的每一項的冪的規律，可以得到一種生成循環的方法，使得該算法從基于遞歸變成基于循環，但是必須是動態生成的循環，于是利用一些Mathematica的元編程技巧，可以設計出一套基于Sum的代碼，而Sum又有ParallelSum作為其并行版本，可以直接無縫移植。對于4項式的300次方，代碼（已打碼）如下圖所示，可以在不到1秒內完成。

如下圖所示，三種算法的計算時間有顯著差異，但三種都呈現出指數級增長的態勢，因為這是一個NP問題。

如有相關需要，歡迎通過公眾號“320科技工作室”聯系我們