一、NP 完全问题 - 布尔可满足性问题 ★

布尔可满足性问题 ( Boolean Satisfiability Problem , SAT ) , 是历史已经找到了一个 $\mathrm{N}\mathrm{P}$ 完全问题 ;

布尔逻辑公式 : 原子命题变元 $\mathrm{x},\mathrm{y},\cdots$ 通过 联结词 合取 $\wedge$ , 析取 $\vee$ , 否定 $\neg$ , 将这些变元联结在一起 , 得到一个布尔逻辑公式 ;

参考 离散数学 - 数据逻辑 - 命题与联结词 博客 : 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )

布尔逻辑公式可满足 , 指的是 存在一个赋值 , 该赋值是从原始命题到真和假的映射 , 是语法到语义的纽带 , 该赋值使得布尔逻辑公式取值为真 , 则称该 布尔逻辑公式可满足 ;

存在一个赋值 , 使得布尔逻辑公式为真 , 该布尔逻辑公式就是可满足的 ;

将 所有 可满足的布尔逻辑公式 , 放在一起 , 组成一个整体 , 称为 布尔可满足性问题 ( Boolean Satisfiability Problem , SAT ) ;

布尔可满足性问题 是 $\mathrm{N}\mathrm{P}$ 完全的 ;

二、布尔可满足性问题是 NP 完全问题证明思路

布尔可满足性问题是 NP 完全问题证明思路 :

① 首先证明 布尔可满足性问题 是 $\mathrm{N}\mathrm{P}$ 问题 ;

证明该步骤 , 只需要验证 , 给定布尔逻辑公式 , 给定一个赋值 , 验证该公式在该赋值的情况下 , 取值为真即可 ;

验证过程所花的时间与联结词个数有关 , 联结词的个数 , 肯定布会超过布尔逻辑公式的长度 ,

验证所花费的时间一定是 多项式时间 ,

因此 布尔可满足性问题 在 $\mathrm{N}\mathrm{P}$ 中 ;

② 再证明 布尔可满足性问题 $\mathrm{S}\mathrm{A}\mathrm{T}$ 是最难的 $\mathrm{N}\mathrm{P}$ 问题 ;

将 布尔可满足性问题 与 $\mathrm{N}\mathrm{P}$ 中每个计算问题 进行比较 ,

证明 $\mathrm{N}\mathrm{P}$ 中的任何计算问题 , 其难易程度 , 布会超过 布尔可满足性问题 ,

即 $\mathrm{N}\mathrm{P}$ 中的任何计算问题 , 都可以在 多项式时间规约到 $\mathrm{S}\mathrm{A}\mathrm{T}$ , 即 $\le \mathrm{S}\mathrm{A}\mathrm{T}$ ,

该证明是很难的 ;

从 $\mathrm{N}\mathrm{P}$ 中 任选一个计算问题 $\mathrm{A}$ ,

$\mathrm{A}$ 是 $\mathrm{N}\mathrm{P}$ 的 , 一定存在一个 非确定性图灵机 可以判定 ( 解决 ) 该问题 , 该 非确定性图灵机 的计算复杂度一定是个多项式 $\mathrm{O}({\mathrm{n}}^{\mathrm{k}})$ ,

证明该问题 $\mathrm{A}$ 一定可以在 多项式时间规约到 $\mathrm{S}\mathrm{A}\mathrm{T}$ , 符号化表示 : $\mathrm{A}\le \mathrm{S}\mathrm{A}\mathrm{T}$ ,

给定一个 字符串 $\mathrm{w}$ , 可以被 非确定性图灵机 $\mathrm{N}$ 接受 , 从 字符串 $\mathrm{w}$ 和 非确定性图灵机 $\mathrm{N}$ 出发 , 在 多项式时间 内构造出一个逻辑公式 ,

非确定性图灵机 $\mathrm{N}$ 接受 字符串 $\mathrm{w}$ , 当且仅当 构造出的逻辑公式是可满足的 ;

构造该逻辑公式 :

构造如下表格 , 将整个 非确定性图灵机 $\mathrm{N}$ 在字符串上作一个计算 , 计算的分支 , 通过一个表格装进去 ;

表格的 长和宽 都是 ${\mathrm{n}}^{\mathrm{k}}$ ,

使用 布尔逻辑公式 表达该表格 , 使得它可以满足一定的条件 ;

引入如下概念 :

引入字符集 : $\mathrm{N}$ 是非确定性图灵机 , 其中 $\mathrm{Q}$ 是 $\mathrm{N}$ 的状态集 , $\Gamma$ ( 伽马 ) 是 $\mathrm{N}$ 的带子的字符集 , 则有 字符集 $\mathrm{C}=\mathrm{Q}\cup \mathrm{\Gamma }\cup \{\#\}$ ;

引入原子命题变元 : ${\mathrm{x}}_{\mathrm{i},\mathrm{j},\mathrm{s}}$ , 其中 $\mathrm{i},\mathrm{j}$ 都是 $[1,{\mathrm{n}}^{\mathrm{k}}]$ 区间内的值 , 每个 $\mathrm{s}$ 都是 字符集 $\mathrm{C}$ 中的字符 ;

上述 ${\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{s}}$ 变元的含义是 , 如果该命题变元 ${\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{s}}$ 取值为真 , 当且仅当 $\mathrm{i},\mathrm{j}$ 格子 ( 水平为 $\mathrm{i}$ , 垂直为 $\mathrm{j}$ 的格子 Cell ) 对应的字符是 $\mathrm{s}$ ;

得到布尔逻辑公式 : 上述表格中的格子中 , 任何格子 , 只包含一个字符 , 并且只能包含一个字符 , 该公式的长度是多项式长度 ; 公式如下 :

ϕ c e l l = ∧ 1 ≤ i , j ≤ n k [ ( ∨ s ∈ C x i , j , s ) ∧ ( ∨ s , t ∈ C s ≠ t ( ¬ x i , j , s ∨ ¬ x i , j , t ) ) ] \rm \phi_{cell} =

开始格局 : 表格中的第一行是 开始格局 , 在所有的表格中 , 一定包含了一个接受格局 , 其中一定包含了有一个状态 , 是接受状态 ;

${\varphi }_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}={\mathrm{x}}_{1,1,\#}\wedge {\mathrm{x}}_{1,2,{\mathrm{q}}_0}\wedge {\mathrm{x}}_{1,3,{\mathrm{w}}_1}\wedge \cdots \wedge {\mathrm{x}}_{1,\mathrm{n}+2,{\mathrm{w}}_{\mathrm{n}}}\wedge {\mathrm{x}}_{1,{\mathrm{n}}^{\mathrm{k}}-1,\mathrm{B}}\wedge {\mathrm{x}}_{1,{\mathrm{n}}^{\mathrm{k}},\#}$

${\varphi }_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}}={\vee }_{1\le \mathrm{i},\mathrm{j}\le {\mathrm{n}}^{\mathrm{k}}}{\mathrm{x}}_{\mathrm{i},\mathrm{j},{\mathrm{q}}_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}}}$

转换函数 : 存在一个 $2\times 3$ 的窗口 , 如果是合法的话 , 该表格中的内容 , 刚好是 非确定性图灵机 的 计算树 中的计算分支内容 ;

ϕ m o v e = ⋀ 1 < i ≤ n k 1 < j < n k     ( 窗 口   ( i , j )   是 合 法 的 ) \rm \phi_{move} =

⋁ a 1 , ⋯   , a 6 l e g a l w i n d o w = ( x i , j − 1 , a 1 ∧ x i , j , a 2 ∧ x i , j + 1 , a 3 ∧ x i + 1 , j − 1 , a 4 ∧ x i + 1 , j , a 5 ∧ x i + 1 , j + 1 , a 6 ) \rm

合并命题公式集合 : 将上述构造出的所有的命题公式 , 放在一起 , 就得到如下公式 :

$\varphi ={\varphi }_{\mathrm{c}\mathrm{e}\mathrm{l}\mathrm{l}}\wedge {\varphi }_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\wedge {\varphi }_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}}\wedge {\varphi }_{\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}}$

$\varphi$ 的长度是 多项式长度 ,

可以将 $\mathrm{N}\mathrm{P}$ 中的任何计算问题 在 多项式时间中规约到 $\mathrm{S}\mathrm{A}\mathrm{T}$ 问题 ( 布尔可满足性问题 ) , 布尔可满足性问题 是 $\mathrm{P}$ 中最难的问题 , 因此该问题是 $\mathrm{N}\mathrm{P}$ 完全问题 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111195716