【计算理论】计算复杂性 ( 多项式等价 | P 类 | 丘奇-图灵论题延伸 )

文章目录

• 一、多项式等价
• 二、P 类
• 三、丘奇-图灵论题延伸

一、多项式等价

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

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

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

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

二、P 类

时间复杂度类 :

定义 时间复杂度类

,

是一个语言 , 对应一个计算问题 , 如果可以被 单个带子的图灵机

进行判定的话 , 它的 时间复杂度是

;

符号化表示 :

类 :

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

将这些问题放在一起 ( 广义并集

) , 组成一个整体 , 就称为

符号化表示 :

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

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

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

三、丘奇-图灵论题延伸

丘奇-图灵论题 : 图灵机 为 算法 提供了一个严格的数学定义 ;

丘奇-图灵论题延伸 :

类 为 有效算法 提供了一个严格的数学定义 ;