假設現在我們已經會做 3-SAT 了，那麼對於一般的 SAT 問題，如果
有一個子句超過三個字符，例如 c1=a1∨a2∨a3∨a4，那麼我們就新增一個變數叫 b，然後
造出兩個新的子句 d =a1 ∨a2 ∨b、 d =~b∨a3 ∨a4。這兩個新的子句都比原來的短，而且
注意到、這兩個新的子句可滿足、若且唯若原來的子句 c1 可滿足。透過反覆這樣的操作，
我們總是可以把任何的子句拆成若干個子句、使得每一個都不超過三個字符，然後將字符重
複使用就可以讓每一個子句都恰為三個字符。如此一來，就可以套用 3-SAT 的演算法去解原
來的問題了。
故3SAT也是NP-complete.
沒有留言:
張貼留言