一、P 类

时间复杂度类 :

定义 时间复杂度类 $\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(\mathrm{t}(\mathrm{n}))$ , $\mathrm{L}$ 是一个语言 , 对应一个计算问题 , 如果可以被 单个带子的图灵机 $\mathrm{T}\mathrm{M}$ 进行判定的话 , 它的 时间复杂度是 $\mathrm{O}(\mathrm{t}(\mathrm{n}))$ ;

符号化表示 : $\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(\mathrm{t}(\mathrm{n}))=\{\mathrm{L}:\mathrm{L}是一个语言,该语言可以被时间复杂度\mathrm{O}(\mathrm{t}(\mathrm{n}))的单个带子图灵机识别\}$

$\mathrm{P}$ 类 :

所有 能够被 确定性 单个带子图灵机 , 在 多项式时间 内 , 能够被 判定的计算问题 ,

将这些问题放在一起 ( 广义并集 $\bigcup$ ) , 组成一个整体 , 就称为 $\mathrm{P}$

符号化表示 : $\mathrm{P}={\bigcup }_{\mathrm{k}}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}({\mathrm{n}}^{\mathrm{k}})$

$\mathrm{P}$ 类 , 就是定义 有效算法 所组成的类 ,

有效算法 , 就是在 多项式时间 内 , 可以执行完毕 , 得到一个确定的结果的算法 ;

确定的结果就是 接受状态 , 或 拒绝状态 ;

二、有效算法函数

上述 $\mathrm{P}$ 类 是对 有效算法 进行了严格的数学定义 ;

计算理论的意义就是 证明 有哪些计算问题 , 是不存在有效算法的 , 如果没有确定性的有效算法 , 就需要 找近似的算法 , 解决同样的问题 , 而不是确定性的算法 ;

有效算法是一个函数 , 该函数的主要依赖于 输入字符串大小 ;

如果给定一个确定性图灵机 , 定义其时间复杂度 , 通过 $\mathrm{f}$ 函数进行定义 , $\mathrm{f}$ 函数是从 自然数集 $\mathrm{N}$ 到 自然数集 $\mathrm{N}$ 的映射 ,

符号化表示 : $\mathrm{f}:\mathrm{N}\to \mathrm{N}$ ,

定义域中的自然数 $\mathrm{N}$ 指的是 输入字符串大小 ,

值域中的自然数 $\mathrm{N}$ 指的是 图灵机计算所执行的步数 ;

时间复杂度 $\mathrm{f}(\mathrm{n})$ 定义方式 : 将所有长度为 $\mathrm{n}$ 的字符串 , 依次输入到图灵机中进行计算 , 所有的计算中取最大的计算步数 , 作为 $\mathrm{f}(\mathrm{n})$ 的取值 ;

三、NP 直觉

有两个问题 ,

问题 $\mathrm{A}$ , 花了一天时间 , 找到了解决方案 ,

问题 $\mathrm{B}$ , 已经存在了解决方案 , 读懂该方案 , 花了一天时间 ,

这两个问题 , 在第一印象直觉中 , 问题 $\mathrm{B}$ 更难一些 ;

理解 问题 $\mathrm{B}$ 的解决方案 , 是一个简单的任务 ,

解决 问题 $\mathrm{A}$ , 是更难的任务 ,

两者都花了一天的时间 , 直觉上感觉问题 $\mathrm{B}$ 更难 ;

解决问题 , 一般比 理解解决问题的方案 , 更难一些 ;

类似于 学习 和 科研 的难度 ,

学习 是理解现有解决方案 , 是简单任务 ,

科研 是提出解决方案 , 是比较难的任务 ;

通常情况下 , 一个问题 , 没有答案 , 要找到答案的话 , 需要创造性 ,

如果已经有一个答案 , 验证这个答案的正确性 , 通常 不需要创造性的 , 只需要有理解能力就足够了 ;

四、NP 简介

$\mathrm{P}$ 目的是确定哪些 计算问题 是 可以被 有效解决 的计算问题 ;

$\mathrm{N}\mathrm{P}$ 目的是确定哪些 计算问题 是 可以被 有效验证 的计算问题 ;

验证 : 验证值的是 , 计算问题 已经有正确的答案 , 将正确的答案 , 根据某些有限的指令 , 规则 , 验证 算法的 每一步是否正确 ;

验证 相当于 学习的过程 , 解决 相当于 科研过程 ;

$\mathrm{N}\mathrm{P}$ 对应的计算问题 , 指的是能够 在 多项式时间内 , 能够 验证 的计算问题 ;

$\mathrm{P}$ 对应的计算问题 , 指的是能够 在 多项式时间内 , 能够 解决 的计算问题 ;

$\mathrm{P}$ 是包含在 $\mathrm{N}\mathrm{P}$ 中的 : 如果有计算问题 , 在 多项式时间 内能够 解决 , 肯定就能在 多项式时间内 能够 验证 ;

$\mathrm{P}$ 是 $\mathrm{N}\mathrm{P}$ 的子集 ;

五、NP 严格数学定义

$\mathrm{N}\mathrm{P}$ 是 多项式时间 内的 验证机 ;

验证机 : $\mathrm{A}$ 语言 ( 计算问题 ) 的 验证机 $\mathrm{V}$ ;

$<\mathrm{w},\mathrm{c}>$ 含义 : 给定一个 输入 $\mathrm{w}$ , $\mathrm{w}$ 是输入字符串 , $\mathrm{c}$ 是输入 $\mathrm{w}$ 被接受的情况下的输入 , 即正确的输入 ;

$\mathrm{A}$ 语言 ( 计算问题 ) 的 验证机 $\mathrm{V}$ 条件 : 给定了正确的输入 $\mathrm{c}$ , 让验证机 $\mathrm{V}$ 进行一步步验证 , 如果 验证机 $\mathrm{V}$ 接受了输入的字符串 $\mathrm{c}$ , 称 验证机 $\mathrm{V}$ 就是计算问题 $\mathrm{A}$ 的验证机 ;

符号化表示 : $\mathrm{A}=\{\mathrm{w}:验证机\mathrm{V}接受<\mathrm{w},\mathrm{c}>中正确的输入\mathrm{c}\}$

验证操作 : 已经有了正确答案 $\mathrm{c}$ , 有一个有限的规则 , 将正确答案 $\mathrm{c}$ 每一步 , 代入有限规则中进行验证是否正确 ;

验证时间 : 已经有了正确答案 $\mathrm{c}$ , 有一个有限的规则 , 将正确答案 $\mathrm{c}$ 每一步 , 代入有限规则中进行验证是否正确 , 最后记录整个验证过程所花费的时间 ; 即 学习的过程 ;

$\mathrm{N}\mathrm{P}$ 计算问题要求 : 如果花费的时间 在 多项式时间 之内 , 就称 该问题是 $\mathrm{N}\mathrm{P}$ 对应的计算问题 ;

多项式时间验证机 : $\mathrm{A}$ 语言 如果 可以在 多项式时间 内 可以 验证 的话 , 就称该语言 有一个 多项式时间验证机 ;

$\mathrm{N}\mathrm{P}$ 类就是有 多项式时间验证机 的 语言 ( 计算问题 ) 的总体集合 ;

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

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