← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.782Z

in ϕ‴: If Ci contains three distinct literals, then simply include Ci as a clause of ϕ‴.

If Ci contains exactly two distinct literals, that is, if Ci = (l1 ∨ l2), where l1 and l2 are literals, then include (l1 ∨ l2 ∨ p) ∧ (l1 ∨ l2 ∨ ¬p) as clauses of ϕ‴. The literals p and ¬p merely fulfill the syntactic requirement that each clause of ϕ‴ contain exactly three distinct literals. Whether p = 0 or p = 1, one of the clauses is equivalent to l1 ∨ l2, and the other evaluates to 1, which is the identity for AND. If Ci contains just one distinct literal l, then include (l ∨p ∨q)∧(l ∨ p ∨ ¬q) ∧ (l ∨ ¬p ∨ q) ∧ (l ∨ ¬p ∨ ¬q) as clauses of ϕ‴. Regardless of the values of p and q, one of the four clauses is equivalent to l, and the other three evaluate to 1.

We can see that the 3-CNF formula ϕ‴ is satisfiable if and only if ϕ is satisfiable by in

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea