壮心未与年俱老，死去犹能作鬼雄。这篇文章主要讲述Satisfiability相关的知识，希望能为你提供帮助。
目录
-
1.1 SAT
- 1.1.1 3-SAT
- 1.1.2 3-satisfiability reduces to independent set
- 1.1.3 必要性
- 1.1.4 充分性
1.1 SATSAT. Given a CNF formula Φ, does it have a satisfying truth assignment?
可满足性要求的是结果为TRUE！
1.1.1 3-SAT
SAT： where each clause contains exactly 3 literals
(and each literal corresponds to a different variable).
先来看一个列子：
文章图片
当然一个正确的实例是非常好找到的！（那么有没有可能永远找不到解？）答案是肯定！原因见下文。
1.1.2 3-satisfiability reduces to independent set
Pf. Given an instance Φ of 3-SAT, we construct an instance (G, k) of
INDEPENDENT-SET that has an independent set of size k = ?Φ? iff Φ is satisfiable.
定理：3元可满足性问题可以规约到独立集问题。
Construction.
- G contains 3 nodes for each clause, one for each literal.
- Connect 3 literals in a clause in a triangle.
- Connect literal to each of its negations
文章图片
1.1.3 必要性
定理：Φ is satisfiable iff G contains an independent set of size k = ?Φ?.
Pf.
? Consider any satisfying assignment for Φ.
- Select one true literal from each clause/triangle.
- This is an independent set of size k = ?Φ?.
文章图片
定理：Φ is satisfiable iff G contains an independent set of size k = ?Φ?.
Pf. ? Let S be independent set of size k.
- S must contain exactly one node in each triangle.
- Set these literals to true (and remaining literals consistently).
- All clauses in Φ are satisfied.
文章图片
推荐阅读
- XML – E4X概述
- 消息列队基础
- 滤镜也能复制粘贴（视频编辑服务专属滤镜一键搞定）
- P VS NP
- Linux之tar命令
- Kubernetes Cronjob的第一次使用
- 9DNS主从和iptables使用
- JVM升级篇八（工具篇）
- 更便捷的Mybatis插件——EasyMybatis