NP-Completeness

---

In 1970s, Stephen Cook and Leonid Levin discovered certain problems in NP whose individual complexity is related to that of the entire class.

If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable.

These problems are called NP-complete. In this section, we introduce some classic NP-complete problems.

Venn diagram, some relations are not proven

Polynomial Time Reduction

NoteDefinition: Polynomial Time Computable Function

A function \(f : \Sigma^* \to \Sigma^*\) is a polynomial time computable function if some polynomial time Turing machine exists that halts with just \(f(w)\) on its tape, when started on any input \(w\).

NoteDefinition: Polynomial Time Reducibility

Let \(A, B \subseteq \Sigma^*\). Then \(A\) is polynomial time mapping reducible (or simply polynomial time reducible) to \(B\), written \(A \leq_P B\), if a polynomial time computable function \(f : \Sigma^* \to \Sigma^*\) exists, where for every \(w\):

\[ w \in A \iff f(w) \in B \]

The function \(f\) is called the polynomial time reduction of \(A\) to \(B\).

Theorem: \(A \leq_P B \land B \in P \Rightarrow A \in P\).

NoteProof

设 \(M_B\) 是在多项式时间内判定 \(B\) 的 TM，\(f\) 是 \(A \leq_P B\) 的多项式时间归约函数。构造判定 \(A\) 的 TM \(M_A\)：

\(M_A\) on input \(w\):

1. 计算 \(f(w)\)
2. 在 \(f(w)\) 上运行 \(M_B\)，输出 \(M_B\) 的结果

由于 \(f\) 和 \(M_B\) 都在多项式时间运行，复合后仍为多项式时间。

Q.E.D.

---

NP-Completeness

NoteDefinition: NP-Complete

A language \(B\) is NP-complete if it satisfies two conditions:

1. \(B \in \mathrm{NP}\), and
2. Every \(A \in \mathrm{NP}\) is polynomial time reducible to \(B\) (i.e., \(A \leq_P B\)).

If \(B\) only satisfies condition 2, it is called NP-hard.

NP-complete 问题是 NP 中”最难”的问题。以下两个定理说明了为什么它们如此重要：

Theorem: If \(B\) is NP-complete and \(B \in P\), then \(P = NP\).

NoteProof

若 \(B \in P\) 且 \(B\) 是 NP-complete，则对任意 \(A \in \mathrm{NP}\)，有 \(A \leq_P B\)。由 \(A \leq_P B \land B \in P \Rightarrow A \in P\)，可知 \(A \in P\)。因此 \(\mathrm{NP} \subseteq P\)，又 \(P \subseteq \mathrm{NP}\)，故 \(P = \mathrm{NP}\)。

Q.E.D.

Theorem: If \(B\) is NP-complete, \(B \leq_P C\) for some \(C \in \mathrm{NP}\), then \(C\) is NP-complete.

NoteProof

已知 \(C \in \mathrm{NP}\)。对任意 \(A \in \mathrm{NP}\)，由 \(B\) 的 NP-completeness 知 \(A \leq_P B\)。又 \(B \leq_P C\)，由 \(\leq_P\) 的传递性得 \(A \leq_P C\)。故 \(C\) 满足 NP-complete 的两个条件。

Q.E.D.

这意味着：要证明一个新问题 \(C\) 是 NP-complete，只需 (1) 证明 \(C \in \mathrm{NP}\)；(2) 找到一个已知的 NP-complete 问题 \(B\)，证明 \(B \leq_P C\)。

graph TD
    SAT["SAT (Cook-Levin)"]
    TSAT["3SAT"]
    CLIQUE["CLIQUE"]
    VC["VERTEX-COVER"]
    HAMPATH["HAMPATH"]
    UHAMPATH["UHAMPATH"]
    SUBSETSUM["SUBSET-SUM"]
    
    SAT -->|"≤P"| TSAT
    TSAT -->|"≤P"| CLIQUE
    TSAT -->|"≤P"| VC
    TSAT -->|"≤P"| HAMPATH
    HAMPATH -->|"≤P"| UHAMPATH
    TSAT -->|"≤P"| SUBSETSUM

---

SAT

NoteDefinition: SAT (Satisfiability Problem)

• Boolean variables are assigned to TRUE (1) or FALSE (0).
• Boolean operations are AND (\(\land\)), OR (\(\lor\)), and NOT (\(\lnot\)).
• A Boolean formula is an expression involving Boolean variables and operations.
• A Boolean formula is satisfiable if some assignment makes the formula evaluate to 1.
• The satisfiability problem is to test whether a Boolean formula is satisfiable:

\[ \text{SAT} = \{\langle \phi \rangle \mid \phi \text{ is a satisfiable Boolean formula}\} \]

Cook-Levin Theorem

Theorem (Cook-Levin): \(\mathrm{SAT}\) is NP-complete.

NoteProof

Part 1: \(\mathrm{SAT} \in \mathrm{NP}\)

非确定性 TM 猜测一个对所有变量的赋值，然后在多项式时间内验证该赋值是否使公式为真。

Part 2: \(\mathrm{SAT}\) is NP-hard

设 \(A \in \mathrm{NP}\)，令 \(N\) 为在 \(O(n^k)\) 时间内判定 \(A\) 的 NTM。对输入 \(w\)（长度 \(n\)），构造布尔公式 \(\phi\) 使得 \(w \in A \iff \phi\) 可满足。

Tableau（画面表）构造：\(N\) 在输入 \(w\) 上的一个接受计算分支可表示为 \(n^k \times n^k\) 的表格（tableau），其中：

• 每一行是 \(N\) 的一个配置（configuration）
• 第一行是起始配置
• 每相邻两行之间按转移函数合法转移
• 某一行包含 \(q_{\text{accept}}\)

graph TD
    subgraph tab["Tableau n^k × n^k"]
        direction TB
        Row1["# q₀ w₁ w₂ ⋯ wₙ ⊔ ⋯ ⊔ #  (start config)"]
        Row2["⋯ (config after 1 step) ⋯"]
        RowDots["⋮"]
        RowEnd["⋯ qaccept ⋯  (accepting config)"]
    end
    Row1 --> Row2
    Row2 --> RowDots
    RowDots --> RowEnd

令 \(C = Q \cup \Gamma \cup \{\#\}\) 为配置字母表。引入布尔变量 \(x_{i,j,s}\)，其中 \(1 \leq i, j \leq n^k\)，\(s \in C\)。

\(x_{i,j,s} = 1\) 当且仅当 tableau 的第 \(i\) 行第 \(j\) 列为符号 \(s\)。

构造 \(\phi = \phi_{\text{cell}} \land \phi_{\text{start}} \land \phi_{\text{move}} \land \phi_{\text{accept}}\)：

\(\phi_{\text{cell}}\)：每个格子恰好包含一个符号。

\[ \phi_{\text{cell}} = \bigwedge_{1 \leq i,j \leq n^k} \left[ \left(\bigvee_{s \in C} x_{i,j,s}\right) \land \bigwedge_{s \neq t \in C} (\lnot x_{i,j,s} \lor \lnot x_{i,j,t}) \right] \]

\(\phi_{\text{start}}\)：第一行是起始配置 \(\# \, q_0 \, w_1 \, w_2 \cdots w_n \, \sqcup \cdots \sqcup \, \#\)。

\[ \phi_{\text{start}} = x_{1,1,\#} \land x_{1,2,q_0} \land x_{1,3,w_1} \land \cdots \land x_{1,n+2,w_n} \land x_{1,n+3,\sqcup} \land \cdots \land x_{1,n^k,\#} \]

\(\phi_{\text{accept}}\)：某一行中出现 \(q_{\text{accept}}\)。

\[ \phi_{\text{accept}} = \bigvee_{1 \leq i,j \leq n^k} x_{i,j,q_{\text{accept}}} \]

\(\phi_{\text{move}}\)：每个 \(2 \times 3\) 窗口都是合法的（legal window）。

对 tableau 中每个位置 \((i, j)\)（\(1 < i \leq n^k\), \(1 < j < n^k\)），检查由第 \(i-1, i\) 行、第 \(j-1, j, j+1\) 列构成的 \(2 \times 3\) 窗口。窗口合法当且仅当它符合 \(N\) 的转移函数。

\[ \phi_{\text{move}} = \bigwedge_{1 < i \leq n^k,\; 1 < j < n^k} \text{(window}_{i,j} \text{ is legal)} \]

合法窗口的关键观察：如果窗口顶行三个符号中不包含任何状态符号（\(q \in Q\)），则底行必须与顶行完全一致（因为 TM 头不在此处，内容不变）。只有当顶行含状态符号时，底行才可能不同，且必须符合转移函数。

合法窗口举例（设 \(\delta(q_1, a) \ni \{(q_1, b, R)\}\)）：

顶行	底行	合法？	原因
\(a \quad b \quad a\)	\(a \quad b \quad a\)	合法	无状态，内容不变
\(a \quad q_1 \quad b\)	\(a \quad b \quad q_1\)	合法	头读 \(b\)，写 \(b\)，右移
\(a \quad q_1 \quad b\)	\(q_1 \quad b \quad b\)	不合法	头应右移而非左移

多项式规模：\(|C|\) 是常数，变量数 \(O(n^{2k} \cdot |C|)\)，公式长度 \(O(n^{2k})\)，可在多项式时间内从 \(w\) 构造 \(\phi\)。

正确性：\(w \in A\) \(\iff\) \(N\) 在 \(w\) 上有接受计算分支 \(\iff\) 存在合法 tableau \(\iff\) \(\phi\) 可满足。

Q.E.D.

---

3SAT

NoteDefinition: 3SAT

• A literal is a Boolean variable or a negated Boolean variable.
• A clause is several literals connected with \(\lor\)s.
• A Boolean formula is in conjunctive normal form (CNF), called a cnf-formula, if it comprises several clauses connected with \(\land\)s.
• A Boolean formula is a 3cnf-formula if all the clauses have exactly three literals.
• Define:

\[ \text{3SAT} = \{\langle \phi \rangle \mid \phi \text{ is a satisfiable 3cnf-formula}\} \]

Theorem: \(\mathrm{3SAT}\) is NP-complete.

NoteProof

\(\mathrm{3SAT} \in \mathrm{NP}\)：猜测赋值，验证每个子句是否至少有一个文字为真，多项式时间。

NP-hard：由 Cook-Levin 定理的归约过程出发，对生成的 \(\phi\) 做进一步变换，使其成为 3cnf-formula。具体来说，对 \(\phi\) 中的每个子句，按文字数分情况处理：

Case 1: 子句只有 1 个文字 \(\ell_1\)。替换为 \((\ell_1 \lor \ell_1 \lor \ell_1)\)。

Case 2: 子句有 2 个文字 \(\ell_1, \ell_2\)。替换为 \((\ell_1 \lor \ell_2 \lor \ell_2)\)。

Case 3: 子句恰好有 3 个文字。保持不变。

Case 4: 子句有 \(k > 3\) 个文字 \(\ell_1, \ell_2, \ldots, \ell_k\)。引入新的辅助变量 \(z_1, z_2, \ldots, z_{k-3}\)，替换为：

\[ (\ell_1 \lor \ell_2 \lor z_1) \land (\overline{z}_1 \lor \ell_3 \lor z_2) \land (\overline{z}_2 \lor \ell_4 \lor z_3) \land \cdots \land (\overline{z}_{k-3} \lor \ell_{k-1} \lor \ell_k) \]

正确性（Case 4）：原子句 \((\ell_1 \lor \cdots \lor \ell_k)\) 可满足 \(\iff\) 存在 \(z_1, \ldots, z_{k-3}\) 的赋值使所有新子句同时可满足。

若 \(\ell_i = 1\)（某个文字为真），设 \(z_1 = \cdots = z_{i-2} = 1\)，\(z_{i-1} = \cdots = z_{k-3} = 0\)，可验证所有新子句均满足。

反之，若所有 \(\ell_i = 0\)，则第一个子句要求 \(z_1 = 1\)，这迫使第二个子句要求 \(z_2 = 1\)，依此类推，最终最后一个子句无法满足。

归约是多项式时间的：每个长度 \(k\) 的子句产生 \(k - 2\) 个新子句。

Q.E.D.

---

CLIQUE

NoteDefinition: CLIQUE

在无向图 \(G = (V, E)\) 中，团 (clique) 是 \(V\) 的子集，其中任意两个节点之间都有边。\(k\)-clique 是大小为 \(k\) 的团。

\[ \mathrm{CLIQUE} = \{ \langle G, k \rangle \mid G \text{ is an undirected graph with a } k\text{-clique} \} \]

Theorem: \(\mathrm{CLIQUE}\) is NP-complete.

NoteProof

\(\mathrm{CLIQUE} \in \mathrm{NP}\)：猜测 \(k\) 个节点的子集，验证每一对之间是否有边。

NP-hard：证明 \(\mathrm{3SAT} \leq_P \mathrm{CLIQUE}\)。

给定 3cnf-formula \(\phi = C_1 \land C_2 \land \cdots \land C_k\)，其中每个 \(C_i\) 有 3 个文字。构造图 \(G\) 和参数 \(k\)：

构造：

1. 对每个子句 \(C_i = (\ell_1^i \lor \ell_2^i \lor \ell_3^i)\)，创建一个”组”（triple）包含 3 个节点，分别对应三个文字。
2. 连边规则：节点 \(v_a^i\) 与 \(v_b^j\) 之间有边当且仅当：
   • \(i \neq j\)（不在同一组内），且
   • \(\ell_a^i\) 与 \(\ell_b^j\) 不互补（不是 \(x\) 和 \(\overline{x}\) 的关系）

例：\(\phi = (x_1 \lor \overline{x}_2 \lor x_3) \land (\overline{x}_1 \lor x_2 \lor x_3) \land (x_1 \lor x_2 \lor \overline{x}_3)\)

graph LR
    subgraph C1["C₁: x₁ ∨ x̄₂ ∨ x₃"]
        v11(("x₁"))
        v12(("x̄₂"))
        v13(("x₃"))
    end
    subgraph C2["C₂: x̄₁ ∨ x₂ ∨ x₃"]
        v21(("x̄₁"))
        v22(("x₂"))
        v23(("x₃"))
    end
    subgraph C3["C₃: x₁ ∨ x₂ ∨ x̄₃"]
        v31(("x₁"))
        v32(("x₂"))
        v33(("x̄₃"))
    end
    
    v11 --- v22
    v11 --- v23
    v11 --- v32
    v12 --- v22
    v12 --- v23
    v12 --- v31
    v12 --- v32
    v12 --- v33
    v13 --- v22
    v13 --- v23
    v13 --- v31
    v13 --- v32
    v21 --- v32
    v21 --- v33
    v22 --- v31
    v22 --- v32
    v23 --- v31
    v23 --- v32
    v13 --- v21

正确性：

(\(\Rightarrow\)) 若 \(\phi\) 可满足，取一个满足赋值。每个子句 \(C_i\) 中至少有一个文字为真，选一个为真的文字对应的节点。这 \(k\) 个节点构成 \(k\)-clique：来自不同组（满足条件 1），且都为真的文字不可能互补（满足条件 2）。

(\(\Leftarrow\)) 若 \(G\) 有 \(k\)-clique \(S\)，则 \(S\) 中每组恰好一个节点（因为组内无边）。将 \(S\) 中节点对应的文字都设为真——不会矛盾，因为 clique 中的文字不互补。此时每个子句至少一个文字为真，\(\phi\) 可满足。

Q.E.D.

---

VERTEX-COVER

NoteDefinition: VERTEX-COVER

在无向图 \(G = (V, E)\) 中，顶点覆盖 (vertex cover) 是 \(V\) 的子集 \(S\)，使得每条边至少有一个端点在 \(S\) 中。

\[ \mathrm{VERTEX\text{-}COVER} = \{ \langle G, k \rangle \mid G \text{ has a vertex cover of size } k \} \]

Theorem: \(\mathrm{VERTEX\text{-}COVER}\) is NP-complete.

NoteProof

\(\mathrm{VERTEX\text{-}COVER} \in \mathrm{NP}\)：猜测 \(k\) 个节点，验证每条边是否至少一个端点被选中。

NP-hard：证明 \(\mathrm{3SAT} \leq_P \mathrm{VERTEX\text{-}COVER}\)。

给定 3cnf-formula \(\phi\)，含 \(m\) 个变量 \(x_1, \ldots, x_m\) 和 \(l\) 个子句 \(C_1, \ldots, C_l\)。构造图 \(G\) 和参数 \(k = m + 2l\)。

构造：

1. 变量小工具 (variable gadget)：对每个变量 \(x_i\)，创建一条边连接节点 \(x_i\) 和 \(\overline{x}_i\)。覆盖这条边至少选一个端点——对应将 \(x_i\) 设为 TRUE 或 FALSE。

2. 子句小工具 (clause gadget)：对每个子句 \(C_j = (\ell_1 \lor \ell_2 \lor \ell_3)\)，创建 3 个新节点 \(a_1^j, a_2^j, a_3^j\) 构成三角形（两两连边）。

3. 连接边：\(a_r^j\) 连向对应文字 \(\ell_r\) 在变量小工具中的节点。

graph TD
    subgraph VG["Variable Gadgets"]
        x1(("x₁")) --- nx1(("x̄₁"))
        x2(("x₂")) --- nx2(("x̄₂"))
        x3(("x₃")) --- nx3(("x̄₃"))
    end
    subgraph CG["Clause: (x₁ ∨ x̄₂ ∨ x₃)"]
        a1(("a₁")) --- a2(("a₂"))
        a2 --- a3(("a₃"))
        a3 --- a1
    end
    a1 -.- x1
    a2 -.- nx2
    a3 -.- x3

参数：\(k = m + 2l\)（每个变量小工具选 1 个端点，每个三角形选 2 个节点）。

正确性：

(\(\Rightarrow\)) 若 \(\phi\) 可满足：变量小工具中选为真的文字对应的节点（共 \(m\) 个）。对每个三角形，至少一个节点的连接边已经被变量节点覆盖（因为对应文字为真），选三角形中另外两个节点。总共 \(m + 2l = k\) 个节点，覆盖所有边。

(\(\Leftarrow\)) 若 \(G\) 有大小 \(k\) 的顶点覆盖：每个变量小工具恰好选 1 个（否则三角形不够覆盖），三角形恰好选 2 个。三角形中未被选的节点，其连接边必须由变量端覆盖，这意味着对应文字在变量小工具中被选中（为真），因此每个子句至少有一个文字为真。

Q.E.D.

---

HAMPATH

NoteDefinition: HAMPATH

哈密顿路径 (Hamiltonian path) 是经过图中每个节点恰好一次的有向路径。

\[ \mathrm{HAMPATH} = \{ \langle G, s, t \rangle \mid G \text{ is a directed graph with a Hamiltonian path from } s \text{ to } t \} \]

Theorem: \(\mathrm{HAMPATH}\) is NP-complete.

NoteProof

\(\mathrm{HAMPATH} \in \mathrm{NP}\)：猜测节点排列，验证相邻节点间有边且起终点正确。

NP-hard：证明 \(\mathrm{3SAT} \leq_P \mathrm{HAMPATH}\)。

给定 3cnf-formula \(\phi\)，含 \(m\) 个变量 \(x_1, \ldots, x_m\) 和 \(l\) 个子句 \(C_1, \ldots, C_l\)。构造有向图 \(G\) 以及起终点 \(s, t\)。

构造：

1. 创建全局起点 \(s\) 和终点 \(t\)。

2. 钻石结构 (diamond)：对每个变量 \(x_i\)，创建一个水平带，包含 \(3l + 1\) 个节点（记为 \(d_{i,0}, d_{i,1}, \ldots, d_{i,3l}\)），相邻节点间双向连边（左右均可通行）。

3. 连接钻石：\(s\) 连向 \(d_{1,0}\) 和 \(d_{1,3l}\)；\(d_{i,3l}\) 和 \(d_{i,0}\) 分别连向 \(d_{i+1,0}\) 和 \(d_{i+1,3l}\)；\(d_{m,3l}\) 和 \(d_{m,0}\) 连向 \(t\)。

4. 子句节点：对每个子句 \(C_j\)，创建节点 \(c_j\)。

5. 子句连接：若变量 \(x_i\) 以正文字出现在 \(C_j\) 中，加边 \(d_{i,3j-2} \to c_j\) 和 \(c_j \to d_{i,3j}\)（从左到右可绕道访问 \(c_j\)）。若以负文字 \(\overline{x}_i\) 出现，加边 \(d_{i,3j} \to c_j\) 和 \(c_j \to d_{i,3j-2}\)（从右到左可绕道访问 \(c_j\)）。

graph TD
    s(("s"))
    t(("t"))
    
    subgraph D1["Diamond for x₁"]
        direction LR
        d10(("0")) <--> d11(("1")) <--> d12(("2")) <--> d13(("3")) <--> d14(("4")) <--> d15(("5")) <--> d16(("6"))
    end
    
    subgraph D2["Diamond for x₂"]
        direction LR
        d20(("0")) <--> d21(("1")) <--> d22(("2")) <--> d23(("3")) <--> d24(("4")) <--> d25(("5")) <--> d26(("6"))
    end
    
    c1(("c₁"))
    c2(("c₂"))
    
    s --> d10
    s --> d16
    d16 --> d20
    d10 --> d20
    d16 --> d26
    d10 --> d26
    d26 --> t
    d20 --> t

正确性：

• 从左到右 走水平带 \(\Leftrightarrow\) \(x_i = \mathrm{TRUE}\)。此时可通过”绕道”（detour）访问正文字子句节点 \(c_j\)。
• 从右到左 走水平带 \(\Leftrightarrow\) \(x_i = \mathrm{FALSE}\)。此时可绕道访问负文字子句节点。
• 哈密顿路径必须经过所有子句节点 \(c_j\)，而 \(c_j\) 只能通过某个绕道到达。
• 如果所有子句都可被满足，则对应赋值确定了每个水平带的方向，绕道覆盖所有 \(c_j\)。
• 反方向同理：哈密顿路径决定了一个满足赋值。

Normality argument: 可以证明任何哈密顿路径在每个水平带上要么完全从左到右，要么完全从右到左（不会在中间跳来跳去），因此路径确实编码了一个合法赋值。

Q.E.D.

---

UHAMPATH

NoteDefinition: UHAMPATH

\[ \mathrm{UHAMPATH} = \{ \langle G, s, t \rangle \mid G \text{ is an undirected graph with a Hamiltonian path from } s \text{ to } t \} \]

Theorem: \(\mathrm{UHAMPATH}\) is NP-complete.

NoteProof

\(\mathrm{UHAMPATH} \in \mathrm{NP}\)：同 HAMPATH。

NP-hard：证明 \(\mathrm{HAMPATH} \leq_P \mathrm{UHAMPATH}\)。将有向图转化为无向图，同时保持哈密顿路径的对应关系。

节点分裂：将有向图 \(G\) 中的每个节点 \(u\) 分裂为三个节点 \(u_{\text{in}}, u_{\text{mid}}, u_{\text{out}}\)，内部连接 \(u_{\text{in}} — u_{\text{mid}} — u_{\text{out}}\)。

边的转换：对于有向边 \(u \to v\)，在无向图 \(G'\) 中加边 \(u_{\text{out}} — v_{\text{in}}\)。

graph LR
    subgraph orig["有向图中 u → v"]
        u((u)) -->|"edge"| v((v))
    end

graph LR
    subgraph conv["无向图中的对应结构"]
        uin(("u_in")) --- umid(("u_mid"))
        umid --- uout(("u_out"))
        uout ---|"对应 u→v"| vin(("v_in"))
        vin --- vmid(("v_mid"))
        vmid --- vout(("v_out"))
    end

起终点：\(s' = s_{\text{out}}\), \(t' = t_{\text{in}}\)。

正确性：\(G\) 中 \(s \to \cdots \to t\) 的哈密顿路径 \(\Leftrightarrow\) \(G'\) 中 \(s_{\text{out}} — \cdots — t_{\text{in}}\) 的哈密顿路径。in-mid-out 的结构强制了”只进不出”的方向性——路径必须从 in 进入，经过 mid，从 out 离开。

Q.E.D.

---

SUBSET-SUM

NoteDefinition: SUBSET-SUM

\[ \mathrm{SUBSET\text{-}SUM} = \{ \langle S, t \rangle \mid S = \{x_1, \ldots, x_k\} \subseteq \mathbb{N} \text{ 且存在子集使其元素之和为 } t \} \]

Theorem: \(\mathrm{SUBSET\text{-}SUM}\) is NP-complete.

NoteProof

\(\mathrm{SUBSET\text{-}SUM} \in \mathrm{NP}\)：猜测子集，验证和为 \(t\)。

NP-hard：证明 \(\mathrm{3SAT} \leq_P \mathrm{SUBSET\text{-}SUM}\)。

给定 3cnf-formula \(\phi\)，含 \(m\) 个变量 \(x_1, \ldots, x_m\) 和 \(l\) 个子句 \(C_1, \ldots, C_l\)。构造集合 \(S\) 和目标 \(t\)。

每个数用 \(m + l\) 位十进制数表示。前 \(m\) 位对应变量，后 \(l\) 位对应子句。

	\(x_1\)	\(x_2\)	\(\cdots\)	\(x_m\)	\(C_1\)	\(C_2\)	\(\cdots\)	\(C_l\)
\(y_1\) (for \(x_1\))	1	0	\(\cdots\)	0	\([x_1 \in C_1]\)	\([x_1 \in C_2]\)	\(\cdots\)	\([x_1 \in C_l]\)
\(z_1\) (for \(\overline{x}_1\))	1	0	\(\cdots\)	0	\([\overline{x}_1 \in C_1]\)	\([\overline{x}_1 \in C_2]\)	\(\cdots\)	\([\overline{x}_1 \in C_l]\)
\(\vdots\)			\(\ddots\)
\(y_m\) (for \(x_m\))	0	0	\(\cdots\)	1	\([x_m \in C_1]\)	\([x_m \in C_2]\)	\(\cdots\)	\([x_m \in C_l]\)
\(z_m\) (for \(\overline{x}_m\))	0	0	\(\cdots\)	1	\([\overline{x}_m \in C_1]\)	\([\overline{x}_m \in C_2]\)	\(\cdots\)	\([\overline{x}_m \in C_l]\)
\(g_1\)	0	0	\(\cdots\)	0	1	0	\(\cdots\)	0
\(h_1\)	0	0	\(\cdots\)	0	1	0	\(\cdots\)	0
\(\vdots\)						\(\ddots\)
\(g_l\)	0	0	\(\cdots\)	0	0	0	\(\cdots\)	1
\(h_l\)	0	0	\(\cdots\)	0	0	0	\(\cdots\)	1
target \(t\)	1	1	\(\cdots\)	1	3	3	\(\cdots\)	3

其中 \([\ell \in C_j]\) 表示”文字 \(\ell\) 出现在子句 \(C_j\) 中则为 1，否则为 0”。

正确性：

• 变量列：\(y_i\) 和 \(z_i\) 在第 \(i\) 列都是 1，选且仅选其中一个使该列和为 1——对应设 \(x_i = \mathrm{TRUE}\) 或 \(\mathrm{FALSE}\)。
• 子句列：满足赋值使每个子句列 \(C_j\) 的和为 1, 2, 或 3（取决于多少个文字为真），再通过选取 \(g_j, h_j\)（各贡献 1）补到恰好 3。
• 无进位：每列最大和 \(\leq 5 < 10\)，因此各列独立，不产生进位。

例：\(\phi = (x_1 \lor \overline{x}_2) \land (\overline{x}_1 \lor x_2)\)，\(m = 2, l = 2\)。

	\(x_1\)	\(x_2\)	\(C_1\)	\(C_2\)
\(y_1\)	1	0	1	0
\(z_1\)	1	0	0	1
\(y_2\)	0	1	0	1
\(z_2\)	0	1	1	0
\(g_1\)	0	0	1	0
\(h_1\)	0	0	1	0
\(g_2\)	0	0	0	1
\(h_2\)	0	0	0	1
\(t\)	1	1	3	3

取 \(x_1 = \mathrm{TRUE}, x_2 = \mathrm{TRUE}\)：选 \(y_1, y_2, g_1, h_1, g_2\)，和 = \(1133 = t\)。 ✓

Q.E.D.