文章目录
一、多项式等价
二、P 类
三、丘奇-图灵论题延伸
一、多项式等价
多项式等价 : 所有的 确定性的计算模型 之间是 相互等价 的 , 两个带子图灵机 与 单个带子图灵机 , 计算相同的问题时 , 它们之间的计算复杂度的差距是平方差别 , 这两个图灵机是等价的 ;
计算理论 研究的对象是计算 , 不是计算模型 , 研究计算的过程中 , 希望 忽略计算模型之间的差异 ,
如 : 三个带子图灵机的计算 与 单个带子图灵机的计算 被认为是 等价的 ;
多项式等价 概念 , 可以忽略掉计算模型之间的差异 ;
二、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 类 为 有效算法 提供了一个严格的数学定义 ;
