【计算理论】计算复杂性 ( NP 完全问题 - 布尔可满足性问题 ★ | 布尔可满足性问题是 NP 完全问题证明思路 ) ★
文章目录
一、NP 完全问题 - 布尔可满足性问题 ★
布尔可满足性问题 ( Boolean Satisfiability Problem , SAT ) , 是历史已经找到了一个
完全问题 ;
布尔逻辑公式 : 原子命题变元
通过 联结词 合取
, 析取
, 否定
, 将这些变元联结在一起 , 得到一个布尔逻辑公式 ;
参考 离散数学 - 数据逻辑 - 命题与联结词 博客 : 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )
布尔逻辑公式可满足 , 指的是 存在一个赋值 , 该赋值是从原始命题到真和假的映射 , 是语法到语义的纽带 , 该赋值使得布尔逻辑公式取值为真 , 则称该 布尔逻辑公式可满足 ;
存在一个赋值 , 使得布尔逻辑公式为真 , 该布尔逻辑公式就是可满足的 ;
将 所有 可满足的布尔逻辑公式 , 放在一起 , 组成一个整体 , 称为 布尔可满足性问题 ( Boolean Satisfiability Problem , SAT ) ;
布尔可满足性问题 是
完全的 ;
二、布尔可满足性问题是 NP 完全问题证明思路
布尔可满足性问题是 NP 完全问题证明思路 :
① 首先证明 布尔可满足性问题 是
问题 ;
证明该步骤 , 只需要验证 , 给定布尔逻辑公式 , 给定一个赋值 , 验证该公式在该赋值的情况下 , 取值为真即可 ;
验证过程所花的时间与联结词个数有关 , 联结词的个数 , 肯定布会超过布尔逻辑公式的长度 ,
验证所花费的时间一定是 多项式时间 ,
因此 布尔可满足性问题 在
中 ;
② 再证明 布尔可满足性问题
是最难的
问题 ;
将 布尔可满足性问题 与
中每个计算问题 进行比较 ,
证明
中的任何计算问题 , 其难易程度 , 布会超过 布尔可满足性问题 ,
即
中的任何计算问题 , 都可以在 多项式时间规约到
, 即
,
该证明是很难的 ;
从
中 任选一个计算问题
,
是
的 , 一定存在一个 非确定性图灵机 可以判定 ( 解决 ) 该问题 , 该 非确定性图灵机 的计算复杂度一定是个多项式
,
证明该问题
一定可以在 多项式时间规约到
, 符号化表示 :
,
给定一个 字符串
, 可以被 非确定性图灵机
接受 , 从 字符串
和 非确定性图灵机
出发 , 在 多项式时间 内构造出一个逻辑公式 ,
非确定性图灵机
接受 字符串
, 当且仅当 构造出的逻辑公式是可满足的 ;
构造该逻辑公式 :
构造如下表格 , 将整个 非确定性图灵机
在字符串上作一个计算 , 计算的分支 , 通过一个表格装进去 ;
表格的 长和宽 都是
,
使用 布尔逻辑公式 表达该表格 , 使得它可以满足一定的条件 ;
引入如下概念 :
引入字符集 :
是非确定性图灵机 , 其中
是
的状态集 ,
( 伽马 ) 是
的带子的字符集 , 则有 字符集
;
引入原子命题变元 :
, 其中
都是
区间内的值 , 每个
都是 字符集
中的字符 ;
上述
变元的含义是 , 如果该命题变元
取值为真 , 当且仅当
格子 ( 水平为
, 垂直为
的格子 Cell ) 对应的字符是
;
得到布尔逻辑公式 : 上述表格中的格子中 , 任何格子 , 只包含一个字符 , 并且只能包含一个字符 , 该公式的长度是多项式长度 ; 公式如下 :
开始格局 : 表格中的第一行是 开始格局 , 在所有的表格中 , 一定包含了一个接受格局 , 其中一定包含了有一个状态 , 是接受状态 ;
转换函数 : 存在一个
的窗口 , 如果是合法的话 , 该表格中的内容 , 刚好是 非确定性图灵机 的 计算树 中的计算分支内容 ;
合并命题公式集合 : 将上述构造出的所有的命题公式 , 放在一起 , 就得到如下公式 :
的长度是 多项式长度 ,
可以将
中的任何计算问题 在 多项式时间中规约到
问题 ( 布尔可满足性问题 ) , 布尔可满足性问题 是
中最难的问题 , 因此该问题是
完全问题 ;
相关文章
- Python实现 “王者农药” 自动刷金币,这思路 “绝了”!
- MySQL经典练习题+解题思路(三)
- [SWPUCTF 2021 新生赛]Do_you_know_http解题思路
- 华为数据中心网络技术创新思路
- pwnhub 绝对防御 出题思路和反思
- 2023年美赛A题思路解析/2023年美国大学生数学建模竞赛A题思路
- redis 实现登陆次数限制的思路详解
- 内网渗透思路探索 之新思路的探索与验证
- 学习Oracle树查询的语法思路(oracle树查询的语法)
- acking解开Linux之谜:探求开拓思路(linuxunp)
- Oracle数据库全量注释极致编程思路(oracle全量注释)
- Redis实现定时任务管理的有效思路(用redis实现时任务)
- 教程 | 看看大神的思路!机器学习界网红 7 分钟教你如何搭建 Chatbot?(中文版)
- 选择器的朋友可以试试这个思路延迟执行归并选择操作
- jquery多行滚动/向左或向上滚动/响应鼠标实现思路及代码
- js火狐下取本地路径实现思路
- ExtjsNumberField后面加单位实现思路
- mysql一次更新(update)多条记录的思路