一、多项式等价

多项式等价 : 所有的 确定性的计算模型 之间是 相互等价 的 , 两个带子图灵机 与 单个带子图灵机 , 计算相同的问题时 , 它们之间的计算复杂度的差距是平方差别 , 这两个图灵机是等价的 ;

计算理论 研究的对象是计算 , 不是计算模型 , 研究计算的过程中 , 希望 忽略计算模型之间的差异 ,

如 : 三个带子图灵机的计算 与 单个带子图灵机的计算 被认为是 等价的 ;

多项式等价 概念 , 可以忽略掉计算模型之间的差异 ;

二、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}$ 类 为 有效算法 提供了一个严格的数学定义 ;

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

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