文章目录
一、P 类
二、有效算法函数
三、NP 直觉
四、NP 简介
五、NP 严格数学定义
一、P 类
时间复杂度类 :
定义 时间复杂度类 T I M E ( t ( n ) ) \rm TIME( t(n) )TIME(t(n)) , L \rm LL 是一个语言 , 对应一个计算问题 , 如果可以被 单个带子的图灵机 T M \rm TMTM 进行判定的话 , 它的 时间复杂度是 O ( t ( n ) ) \rm O(t(n))O(t(n)) ;
符号化表示 : T I M E ( 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 = ⋃ k T I M E ( n k ) \rm P = \bigcup_k TIME( n^k )P=⋃
k
TIME(n
k
)
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 目的是确定哪些 计算问题 是 可以被 有效解决 的计算问题 ;
N P \rm NPNP 目的是确定哪些 计算问题 是 可以被 有效验证 的计算问题 ;
验证 : 验证值的是 , 计算问题 已经有正确的答案 , 将正确的答案 , 根据某些有限的指令 , 规则 , 验证 算法的 每一步是否正确 ;
验证 相当于 学习的过程 , 解决 相当于 科研过程 ;
N P \rm NPNP 对应的计算问题 , 指的是能够 在 多项式时间内 , 能够 验证 的计算问题 ;
P \rm PP 对应的计算问题 , 指的是能够 在 多项式时间内 , 能够 解决 的计算问题 ;
P \rm PP 是包含在 N P \rm NPNP 中的 : 如果有计算问题 , 在 多项式时间 内能够 解决 , 肯定就能在 多项式时间内 能够 验证 ;
P \rm PP 是 N P \rm NPNP 的子集 ;
五、NP 严格数学定义
N P \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 每一步 , 代入有限规则中进行验证是否正确 , 最后记录整个验证过程所花费的时间 ; 即 学习的过程 ;
N P \rm NPNP 计算问题要求 : 如果花费的时间 在 多项式时间 之内 , 就称 该问题是 N P \rm NPNP 对应的计算问题 ;
多项式时间验证机 : A \rm AA 语言 如果 可以在 多项式时间 内 可以 验证 的话 , 就称该语言 有一个 多项式时间验证机 ;
N P \rm NPNP 类就是有 多项式时间验证机 的 语言 ( 计算问题 ) 的总体集合 ;
