文章目录

一、P 类

时间复杂度类 :

定义 时间复杂度类 TIME(t(n))\rm TIME( t(n) )TIME(t(n)) , L\rm LL 是一个语言 , 对应一个计算问题 , 如果可以被 单个带子的图灵机 TM\rm TMTM 进行判定的话 , 它的 时间复杂度是 O(t(n))\rm O(t(n))O(t(n)) ;

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

P\rm PP 类 :

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

将这些问题放在一起 ( 广义并集 ⋃\bigcup⋃ ) , 组成一个整体 , 就称为 P\rm PP

符号化表示 :P=⋃kTIME(nk)\rm P = \bigcup_k TIME( n^k )P=⋃k​TIME(nk)

P\rm PP 类 , 就是定义 有效算法 所组成的类 ,

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

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

二、有效算法函数

上述 P\rm PP 类 是对 有效算法 进行了严格的数学定义 ;

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

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

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

符号化表示 :f:N→N\rm f : N \to Nf:N→N ,

定义域中的自然数 N\rm NN 指的是 输入字符串大小 ,

值域中的自然数 N\rm NN 指的是 图灵机计算所执行的步数 ;

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

三、NP 直觉

有两个问题 ,

问题 A\rm AA , 花了一天时间 , 找到了解决方案 ,

问题 B\rm BB , 已经存在了解决方案 , 读懂该方案 , 花了一天时间 ,

这两个问题 , 在第一印象直觉中 , 问题 B\rm BB 更难一些 ;

理解 问题 B\rm BB 的解决方案 , 是一个简单的任务 ,

解决 问题 A\rm AA , 是更难的任务 ,

两者都花了一天的时间 , 直觉上感觉问题 B\rm BB 更难 ;

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

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

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

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

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

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

四、NP 简介

P\rm PP 目的是确定哪些 计算问题 是 可以被 有效解决 的计算问题 ;

NP\rm NPNP 目的是确定哪些 计算问题 是 可以被 有效验证 的计算问题 ;

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

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

NP\rm NPNP 对应的计算问题 , 指的是能够 在 多项式时间内 , 能够 验证 的计算问题 ;

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

P\rm PP 是包含在 NP\rm NPNP 中的 :如果有计算问题 , 在 多项式时间 内能够 解决 , 肯定就能在 多项式时间内 能够 验证 ;

P\rm PP 是 NP\rm NPNP 的子集 ;

五、NP 严格数学定义

NP\rm NPNP 是 多项式时间 内的 验证机 ;

验证机 :A\rm AA 语言 ( 计算问题 ) 的 验证机 V\rm VV ;

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

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

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

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

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

NP\rm NPNP 计算问题要求 :如果花费的时间 在 多项式时间 之内 , 就称 该问题是 NP\rm NPNP 对应的计算问题 ;

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

NP\rm NPNP 类就是有 多项式时间验证机 的 语言 ( 计算问题 ) 的总体集合 ;