6.1 從3-SAT到子集合加總#

概念說明#

把 3-SAT 化約到 SUBSET-SUM 是 Karp 的 21 個 NP-complete 問題之一，其構造精巧地利用了十進位（或任意進位）數字的加法不進位特性。核心想法：為每個變數 xᵢ 建立一個「選 xᵢ 為真」的數字，為每個子句 Cⱼ 建立輔助數字，使得「子集和恰好等於目標值」⟺「存在滿足指派」。

構造方式：設有 n 個變數、m 個子句。每個數字有 n + m 個位數，用基底 b = 10（或更大的進位避免進位干擾）。目標值 t 的前 n 位都是 1（表示每個變數恰須有一個文字為真），後 m 位都是 3（表示每個子句須被滿足「三次計票」）。

變數 xᵢ 對應兩個數字：vᵢ（正文字，第 i 位為 1）與 ¬vᵢ（負文字，第 i 位為 1）。兩者只能選一個，因此第 i 位的總和恰為 1。
子句 Cⱼ 對應兩個輔助數字 aⱼ、bⱼ：若某變數的文字出現在 Cⱼ 中，則該變數的兩個數字在第 n + j 位也各為 1；輔助數字該位為 1。
目標第 n + j 位為 3：即使三個文字都選真只有 3 票，選真的文字不足時可由輔助數字補足，最多補 2，故不會超位、也不會進位。

這樣，「能否選出總和為 t 的子集」就完全等價於「能否滿足所有子句」。這個化約是多項式時間：共 2n + 2m 個數字、每個數字 n + m 位，構造時間 O((n + m)²)。

演算法步驟#

輸入：n 個變數、m 個子句，每個子句為文字列表（整數編碼）。
建立 2n + 2m 個數字，每個以長度 n + m 的位數陣列表示。
對變數 xᵢ：正文字數字在位置 i 設 1，並在其出現的每個子句 j 的位置 n + j 設 1；負文字數字同理。
對子句 Cⱼ：兩個輔助數字都在位置 n + j 設 1。
目標 t：前 n 位為 1、後 m 位為 3。
用第 5.2 節的 SUBSET-SUM 求解器解之；若有解，從選中的數字還原變數指派（正文字數字被選 ⟺ xᵢ = True）。

Python 程式碼範例#

def sat_to_subset_sum(n, clauses):
    """3-SAT -> SUBSET-SUM 化約，回傳 (數字列表, 目標值, 名稱)"""
    m = len(clauses)
    width = n + m
    nums, names = [], []

    def make_digit(pos_list):
        d = [0] * width
        for p in pos_list:
            d[p] = 1
        return d

    for i in range(1, n + 1):
        pos_hits = [n + j for j, c in enumerate(clauses) if i in c]
        neg_hits = [n + j for j, c in enumerate(clauses) if -i in c]
        nums.append(make_digit([i - 1] + pos_hits)); names.append(f"x{i}")
        nums.append(make_digit([i - 1] + neg_hits)); names.append(f"!x{i}")
    for j in range(m):
        nums.append(make_digit([n + j])); names.append(f"a{j}")
        nums.append(make_digit([n + j])); names.append(f"b{j}")

    t = int('1' * n + '3' * m)          # 前 n 位 1、後 m 位 3
    as_int = lambda d: int(''.join(map(str, d)))
    return [as_int(d) for d in nums], t, names

def solve_subset_sum(nums, t):
    """回傳選中的索引（簡化 DP：用大整數集合）"""
    reach = {0: []}
    for idx, s in enumerate(nums):
        new = {}
        for val, sel in reach.items():
            nv = val + s
            if nv <= t and nv not in reach and nv not in new:
                new[nv] = sel + [idx]
        reach.update(new)
    return reach.get(t)

n = 3
clauses = [[1, -2, 3], [-1, 2, -3], [2, 3, -1]]
nums, t, names = sat_to_subset_sum(n, clauses)
sel = solve_subset_sum(nums, t)
print("選中:", [names[i] for i in sel])   # 對應一組滿足指派
assign = {names[i][1:]: (not names[i].startswith('!'))
          for i in sel if names[i].lstrip('!').startswith('x')}
print("指派:", assign)

複雜度分析#

構造：2n + 2m 個數字、每個寬 n + m 位，時間 O((n + m)²)，輸入長度也只成長多項式倍——滿足化約的「多項式時間」要求。
正確性關鍵：每位數總和不超過 3 < 10 = 基底，故無進位，各位獨立成立。
還原指派：O(n + m)。
此化約也反向證實了 SUBSET-SUM 的 NP-hardness：若 SUBSET-SUM 有多項式演算法，3-SAT 也有。

練習#

用上述程式對 5 個隨機 3-SAT 實例執行化約與求解，並寫一個 SAT 驗證器確認還原出的指派確實滿足所有子句。
若某子句只有 2 個文字（不是 3 個），化約會出什麼問題？提示：目標位數 3 無法被湊出。修改構造使其支援 2-SAT 子句混合的公式（加入重複文字或調整輔助數字）。
把基底從 10 換成 4，驗證化約仍然正確；再換成 3，找出會失敗的反例。