下一篇:布尔表达式的可满足性（SAT）与库克列文定理(下)。
文章目录
- 1.布尔表达式可满足性问题（Boolean Satisfiability Problem, SAT）
- 二、形式语言和自动机
-
- 1.形式语言
- 2.自动机
-
- 2.1 有穷自动机
- 2.2 不确定型有穷自动机
- 3. 图灵机
-
- 3.1 图灵机的定义
- 3.2 图灵停机问题（Turing's Halting Problem）
- 3.3 丘奇-图灵论题（Church-Turing Thesis）
- 3.4 通用图灵机（Universal Turing Machine, UTM）
- 3.5 图灵完备性（Turing Completeness）
- 三、P、NP、NP-Complete、NP-Hard
-
- 1. 决定性问题（Decision Problem）和优化问题（Optimization Problem）
-
- 1.1 决定性问题
- 1.2 最优化问题
- 2. 归约（Reduction）
- 3. 抽象问题
- 4. 编码和具体问题
- 5. P问题
-
- 5.1 抽象问题
- 5.2 具体问题
- 5.3 编码的影响
- 6. NP问题
- 6.1 基于验证关系（checking relation/verifier）的定义
- 6.2 基于非确定型图灵机（Nondeterministic Turing Machine, NTM）的定义
-
- 6.2.1 非确定型图灵机
- 6.2.2 利用NTM对NP的定义
- 7. NP完全性
1.布尔表达式可满足性问题（Boolean Satisfiability Problem, SAT）
布尔表达式的可满足性是指布尔表达式(或命题公式)是否有一组真实值，使表达式赋值为真。
如果你没有学过数学逻辑，这是对基本概念的一些介绍： ：指能判断真假的陈述句，常用 p , q , r , ? p,q,r,\cdots p,q,r,?比如明天下雨就是命题，给我快递就不是命题。 ：命题所表达的判断结果只能是真实的（T/ 1 1 1）或假（F/ 0 0 0）。例如命题“ 1 1 = 2 1 1=2 1 1=2方程真值为真， 3 x 4 x = 5 x 3^x 4^x=5^x 3x 4x=5x无整数解”的真值为假（显然 x = 2 x=2 x=2为方程的解）。 ：相当于“无”“非”“没有”等。对于命题 p p p， ¬ p \neg p ¬p与 p p p的真值相反。如 p : 1 + 1 = 3 p:1+1=3 p:1+1=3为假， ¬ p : 1 + 1 ≠ 3 \neg p:1+1\ne3 ¬p:1+1=3为真。 ：相当于“且”“也”等。对于命题 p p p和 q q q， p ∧ q p\land q p∧q为真当且仅当 p p p和 q q q同时为真。 ：相当于“或”。对于命题 p p p和 q q q， p ∨ q p\lor q p∨q为真当且仅当 p p p、 q q q至少有一个为真。 除此之外还有蕴含连接词 → \to →、等价连接词 ↔ \leftrightarrow ↔，但它们都可化为前三种连接词。 ：简单命题的真值是确定的，因而又称为命题常项。例如 p : 1 + 1 = 2 p:1+1=2 p:1+1=2。 ：例如“ q : x + y > 5 q:x+y>5 q:x+y>5”， q q q本身不是命题，但当 x , y x,y x,y给定之后就变成了命题，这种真值可以变化的简单陈述句称为命题变项。 ：命题常项或命题变项由连接词连接而成的复合命题称为命题公式。例如 ¬ p ∧ ( q ∨ ¬ r ) \neg p\land(q\lor\neg r) ¬p∧(q∨¬r)就是将命题变项 p , q , r p,q,r p,q,r由 ¬ , ∧ , ∨ \neg,\land,\lor ¬,∧,∨连接而成的命题公式。在SAT问题中，命题公式是指仅由命题变项、否定连接词 ¬ \neg ¬、合取连接词 ∧ \land ∧、析取连接词 ∨ \lor ∨、括号 ( ) () ()连接而成的表达式。 ：设 A A A为一命题公式， p 1 , p 2 , ⋯ , p n p_1,p_2,\cdots,p_n p1,p2,⋯,pn是其中出现的所有命题变项，给 p 1 , p 2 , ⋯ , p n p_1,p_2,\cdots,p_n p1,p2,⋯,pn指定一组真值，则 A A A的真值唯一确定，称这一组真值为对 A A A的一个或；若该赋值使 A A A为真，则称为，否则称为。例如对于 A : ( p ∨ ¬ q ) ∧ r A:(p\lor\neg q)\land r A:(p∨¬q)∧r，当 p = 1 , q = 0 , r = 1 p=1,q=0,r=1 p=1,q=0,r=1时 A A A为真，故 101 101 101为成真赋值；当 p = 0 , q = 1 , r = 1 p=0,q=1,r=1 p=0,q=1,r=1时 A A A为假，故 011 011 011为成假赋值。 命题公式分为：
- ：命题公式 A A A在所有赋值下都是真的，例如 A : 1 A:1 A:1、 A : p ∨ ¬ p A:p\lor\neg p A:p∨¬p。
- ： A A A在所有赋值下都是假的，例如 A : 0 A:0 A:0、 A : p ∧ ¬ p A:p\land\neg p A:p∧¬p。
- ：若 A A A至少存在一组成真赋值（包含重言式）。例如 A : p ∧ ¬ q A:p\land\neg q A:p∧¬q，当 p = 1 , q = 0 p=1,q=0 p=1,q=0时 A A A为真，故 A A A是可满足式。
因此SAT问题就是判断给定的命题公式是不是可满足式。
例如， A : ¬ p ∨ q A:\neg p\lor q A:¬p∨q（即“（非 p p p）或 q q q”）是可满足的，因为 p = 1 , q = 0 p=1,q=0 p=1,q=0时 A A A为真；但 B : p ∧ ¬ p B:p\land\neg p B:p∧¬p不是可满足的，因为“ p p p”和“非 p p p”显然不可能同时成立。
事实上，这个问题解决起来是极为困难的。诸如 p ∧ ¬ p p\land\neg p p∧¬p之类的式子固然容易判断，但有一些更复杂的，例如 ¬ ( ¬ p ∨ q ) ∧ ¬ ( ¬ ( ¬ q ∧ r ) ∨ ( p ∨ r ) ) \neg(\neg p\lor q)\land\neg(\neg(\neg q\land r)\lor(p\lor r)) ¬(¬p∨q)∧¬(¬(¬q∧r)∨(p∨r))，它事实上是矛盾式，然而我们并不容易看出来。因此，计算机是否能够有效地解决这个问题，就是我们要研究的。
二、形式语言与自动机
1.形式语言
：非空的有穷集合，一般记作 Σ \Sigma Σ。 ：由 Σ \Sigma Σ的符号组成的有穷序列称为字母表 Σ \Sigma Σ上的字符串。例如字母表 Σ = { a , b , c , d } \Sigma=\{a,b,c,d\} Σ={ a,b,c,d}上的字符串有 a a a、 a a aa aa、 b a c d bacd bacd、 a c a a d d c b b d c acaaddcbbdc acaaddcbbdc等。
注意：这里 a a a并不等同于字符
'a'， a a a是一个数学上的抽象符号，它可以取任一字符，如 a = a= a='0'，此时字符串 a a a = aaa= aaa="000"。
：字符串 ω \omega ω所含符号的个数称为 ω \omega ω的长度，记作 ∣ ω ∣ |\omega| ∣ω∣。例如 ∣ a b a ∣ = 3 |aba|=3 ∣aba∣=3， ∣ a c b d d c b a ∣ = 8 |acbddcba|=8 ∣acbddcba∣=8。 ：长度为 0 0 0的字符串，记作 ε \varepsilon ε。 设 a ∈ Σ a\in\Sigma a∈Σ，把 n n n个 a a a组成的字符串 a a ⋯ a aa\cdots a aa⋯a记作 a n a^n an， n ∈ N n\in\mathbb N n∈N。特别地， a 0 = ε a^0=\varepsilon a0=ε。 。若 ω \omega ω是 Σ \Sigma Σ上的字符串，则 ω ∈ Σ ∗ \omega\in\Sigma^* ω∈Σ∗。 ： Σ ∗ \Sigma^* Σ∗的任意子集称作字符串 Σ \Sigma Σ上的形式语言，简称语言。例如， A = { a , b } A=\{a,b\} A={ a,b}， B = { a n ∣ n ∈ N } = { a , a a , a a a , ⋯ } B=\{a^n|n\in\mathbb N\}=\{a,aa,aaa,\cdots\} B={ a 标签： kk系列连接器