【计算理论】计算复杂性 ( P 类

时间复杂度类 :

定义 时间复杂度类 T I M E ( t ( n ) ) \rm TIME( t(n) ) TIME(t(n)) , L \rm L L 是一个语言 , 对应一个计算问题 , 如果可以被 单个带子的图灵机 T M \rm TM TM 进行判定的话 , 它的 时间复杂度是 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 P P 类 :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有两个问题 ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P \rm P P 是 N P \rm NP NP 的子集 ;

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

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

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

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

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

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

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

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

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

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