文章目录
- 一、P 类
- 二、有效算法函数
- 三、NP 直觉
- 四、NP 简介
- 五、NP 严格数学定义
一、P 类
时间复杂度类 :
定义 时间复杂度类
,
是一个语言 , 对应一个计算问题 , 如果可以被 单个带子的图灵机
进行判定的话 , 它的 时间复杂度是
;
符号化表示 :
类 :
所有 能够被 确定性 单个带子图灵机 , 在 多项式时间 内 , 能够被 判定的计算问题 ,
将这些问题放在一起 ( 广义并集
) , 组成一个整体 , 就称为
符号化表示 :
类 , 就是定义 有效算法 所组成的类 ,
有效算法 , 就是在 多项式时间 内 , 可以执行完毕 , 得到一个确定的结果的算法 ;
确定的结果就是 接受状态 , 或 拒绝状态 ;
二、有效算法函数
上述
类 是对 有效算法 进行了严格的数学定义 ;
计算理论的意义就是 证明 有哪些计算问题 , 是不存在有效算法的 , 如果没有确定性的有效算法 , 就需要 找近似的算法 , 解决同样的问题 , 而不是确定性的算法 ;
有效算法是一个函数 , 该函数的主要依赖于 输入字符串大小 ;
如果给定一个确定性图灵机 , 定义其时间复杂度 , 通过
函数进行定义 ,
函数是从 自然数集
到 自然数集
的映射 ,
符号化表示 :
,
定义域中的自然数
指的是 输入字符串大小 ,
值域中的自然数
指的是 图灵机计算所执行的步数 ;
时间复杂度
定义方式 : 将所有长度为
的字符串 , 依次输入到图灵机中进行计算 , 所有的计算中取最大的计算步数 , 作为
的取值 ;
三、NP 直觉
有两个问题 ,
问题
, 花了一天时间 , 找到了解决方案 ,
问题
, 已经存在了解决方案 , 读懂该方案 , 花了一天时间 ,
这两个问题 , 在第一印象直觉中 , 问题
更难一些 ;
理解 问题
的解决方案 , 是一个简单的任务 ,
解决 问题
, 是更难的任务 ,
两者都花了一天的时间 , 直觉上感觉问题
更难 ;
解决问题 , 一般比 理解解决问题的方案 , 更难一些 ;
类似于 学习 和 科研 的难度 ,
学习 是理解现有解决方案 , 是简单任务 ,
科研 是提出解决方案 , 是比较难的任务 ;
通常情况下 , 一个问题 , 没有答案 , 要找到答案的话 , 需要创造性 ,
如果已经有一个答案 , 验证这个答案的正确性 , 通常 不需要创造性的 , 只需要有理解能力就足够了 ;
四、NP 简介
目的是确定哪些 计算问题 是 可以被 有效解决 的计算问题 ;
目的是确定哪些 计算问题 是 可以被 有效验证 的计算问题 ;
验证 : 验证值的是 , 计算问题 已经有正确的答案 , 将正确的答案 , 根据某些有限的指令 , 规则 , 验证 算法的 每一步是否正确 ;
验证 相当于 学习的过程 , 解决 相当于 科研过程 ;
对应的计算问题 , 指的是能够 在 多项式时间内 , 能够 验证 的计算问题 ;
对应的计算问题 , 指的是能够 在 多项式时间内 , 能够 解决 的计算问题 ;
是包含在
中的 : 如果有计算问题 , 在 多项式时间 内能够 解决 , 肯定就能在 多项式时间内 能够 验证 ;
是
的子集 ;
五、NP 严格数学定义
是 多项式时间 内的 验证机 ;
验证机 :
语言 ( 计算问题 ) 的 验证机
;
含义 : 给定一个 输入
,
是输入字符串 ,
是输入
被接受的情况下的输入 , 即正确的输入 ;
语言 ( 计算问题 ) 的 验证机
条件 : 给定了正确的输入
, 让验证机
进行一步步验证 , 如果 验证机
接受了输入的字符串
, 称 验证机
就是计算问题
的验证机 ;
符号化表示 :
验证操作 : 已经有了正确答案
, 有一个有限的规则 , 将正确答案
每一步 , 代入有限规则中进行验证是否正确 ;
验证时间 : 已经有了正确答案
, 有一个有限的规则 , 将正确答案
每一步 , 代入有限规则中进行验证是否正确 , 最后记录整个验证过程所花费的时间 ; 即 学习的过程 ;
计算问题要求 : 如果花费的时间 在 多项式时间 之内 , 就称 该问题是
对应的计算问题 ;
多项式时间验证机 :
语言 如果 可以在 多项式时间 内 可以 验证 的话 , 就称该语言 有一个 多项式时间验证机 ;
类就是有 多项式时间验证机 的 语言 ( 计算问题 ) 的总体集合 ;
