原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
3-CNF-SAT. In order to define 3-CNF satisfiability, we first need to define a few terms.
A literal in a boolean formula is an occurrence of a variable (such as x1) or its negation (¬x1). A clause is the OR of one or more literals, such as x1 ∨ ¬x2 ∨ ¬x3. A boolean formula is in conjunctive normal form, or CNF, if it is expressed as an AND of clauses, and it’s in 3-conjunctive normal form, or 3-CNF, if each clause contains exactly three distinct literals.
For example, the boolean formula (x1 ∨ ¬x1 ∨ ¬x2) ∧ (x3 ∨ x2 ∨ x4) ∧ (¬x1 ∨ ¬x3 ∨ ¬x4) is
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea