有理數解

先換個問題的表達：

對非齊次方程組： 是否有非負整數解，其中 是一個 整數非負矩陣， 是個 整數向量。

我們知道，這個問題要有解，當且僅當 ，所以可以首先 跑個高斯消元判斷是否有解。

若 ,那麼這個方程組有唯一解，可以透過高斯消元直接求出唯一解。

若 ，那麼此方程有無數解，那麼可以搞出通解來：

其中 是特解， 是基礎解系， 是任意常數。

非負整數解

為了方便表達，容我瞎幾把取個名字，下文中用LNE（Linear Nonhomogenous Equations）來表示原問題。

斷言：LNE是NPC的。（沒有找到相關的論文，這個證明是我自己給出的，若是有大神知道相關文獻，還請指出）

證明：

我們嘗試將一個很基礎的NPC問題——SAT（SATISFIABILITY）問題，規約到LNE。

說簡單點就是，我們要證明一個很難很難很難的問題SAT不比我們的LNE更難。

我們首先給出SAT問題的一個例項（instance）：

給出一個集合 ，和 個 的子集，分別為 和 ，是否存在一個 整數規劃，使得：

現在將這個例項等價轉換一下，增加變數，處理掉 ：

聰明的小夥伴可能已經注意到了，現在我們的整數規劃方程已經很接近LNE了。

唯一的不同在於，LNE中，除了變數必須是非負數外，所有的關係都是相等。

所以我們引入非負鬆弛變數來消除不等號（感謝 @史石石石的指正）：

這顯然就是一個LNE問題了。

如果我們有個演算法 ，能解決LNE問題，那麼我們就能用演算法 解決上述例項，從而解決SAT問題。

所以我們多項式時間內將SAT問題規約到了LNE問題。而由於SAT是NPC的，所以LNE也是NPC的。

關於解法

其實這個問題本身就是個整數規劃，所以很適合用整數規劃求解器來解決，CPLEX會是個不錯的選擇。