因為一直都不怎么會 NPC 問題的規約證明，于是記錄一下今天看到的幾個簡單的問題。

首先這里的 NPC 問題都是規約到 3-SAT 上的，3-SAT 問題的即有 (n) 個 (01) 變量 (x_i) 和 (m) 個限制，每個限制為有一個三元組 (C_j=(a,b,c)) 其中 (a,b,cin{x_i,
eg x_i})，對于每一個限制要滿足 (a,b,c) 不能均為 false。

顯然所有的 SAT 問題都可以通過建虛點的形式轉化成 3-SAT 問題。然后有一個 ETH 猜想，即不存在能在 (2^{o(n)}poly(|I|)) 的復雜度內判定 3-SAT 的算法（(I) 指輸入）。

Subset Sum

問對于大小為 (n) 一個集合 (S)，能否從中找到一個子集滿足子集中的元素之和為 (k)。

對于每個變量我們建立兩個元素 (a_i,b_i)，其中 (a_i=10^{i-1}+sum_{x_iin C_j} 10^{n+j-1},b_i=10^{i-1}+sum_{
eg x_iin C_j} 10^{n+j-1}) 第 (i-1) 相當于表示 (x_i) 有沒有賦值，然后第 (n+j-1) 位則表示 (C_j) 有幾個變量的值跟要求是一樣的。然后再對每個限制增加兩個元素 (c_i=d_i=10^{n+j-1}) 用于補不滿足的（補成一定有 (3) 個滿足）。

然后令 (k=sum_{i=1}^{n} 10^{i-1}+sum_{j=1}^{m} 3 cdot 10^{n+j-1}) 做 Subset Sum 即可。

Knapsack

有 (n) 個物品的集合 (S)，每個物品有一個重量 (w_i) 和權值 (v_i)，對于集合 (T) 設 (w(T)=sum_{iin T}w_i,v(T)=sum_{iin T}v_i)。給定背包大小 (C)，求 (max_{w(T)le C} V(T))。

設一個 Subset Sum 問題中的元素為 (a_i)，那么令 (w_i=v_i=a_i,C=k) 做一遍背包然后檢查是否等于 (k) 即可。

從這兩個規約可以看出，Knapsack 問題不存在 (2^{o(sqrt{|I|})}) 復雜度的做法。（根號的原因是將 3-SAT 問題規約到背包我們的值域是 (O(10^m)) 所以輸入是 (O(m^2))）。

然后一個 (2^{O(sqrt{|I|})}) 解決 01 背包問題的方法就是，如果 (nle O(sqrt {|I|})) 就 (2^n) 暴力，否則對于權值最大的 (sqrt n) 個暴力，對于剩下的做值域為 (O(sqrt{|I|})) 的背包就好啦。

無向圖染色問題

給定一個無向圖和 (k) 種顏色，判斷能否染色使得有邊的兩個點不同色。

考慮只有 (3) 種顏色的時候，可以簡單地將或操作通過染色實現，然后就可以規約到 3-SAT 了，具體如下圖。（下面兩個是輸入，上面是輸出）

總結

以上是生活随笔為你收集整理的几个NPC问题的简单规约的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。