有理數解
先換個問題的表達:
對非齊次方程組: 是否有非負整數解,其中 是一個 整數非負矩陣, 是個 整數向量。
我們知道,這個問題要有解,當且僅當 ,所以可以首先 跑個高斯消元判斷是否有解。
若 ,那麼這個方程組有唯一解,可以透過高斯消元直接求出唯一解。
若 ,那麼此方程有無數解,那麼可以搞出通解來:
其中 是特解, 是基礎解系, 是任意常數。
非負整數解
為了方便表達,容我瞎幾把取個名字,下文中用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會是個不錯的選擇。
有理數解
先換個問題的表達:
對非齊次方程組: 是否有非負整數解,其中 是一個 整數非負矩陣, 是個 整數向量。
我們知道,這個問題要有解,當且僅當 ,所以可以首先 跑個高斯消元判斷是否有解。
若 ,那麼這個方程組有唯一解,可以透過高斯消元直接求出唯一解。
若 ,那麼此方程有無數解,那麼可以搞出通解來:
其中 是特解, 是基礎解系, 是任意常數。
非負整數解
為了方便表達,容我瞎幾把取個名字,下文中用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會是個不錯的選擇。