【计算理论】计算复杂性 ( 非确定性图灵机的时间复杂度 | 非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的关系 )

文章目录

• 一、非确定性图灵机的时间复杂度
• 二、非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的指数关系

一、非确定性图灵机的时间复杂度

---

给定一个非确定性图灵机 , 该图灵机是 判定机 , 在所有的输入上都会停机 , 肯定能得到一个 接受状态 或 拒绝状态 结果 ;

非确定性图灵机 计算过程是一个计算树 , 每个计算分支都可以得到一个 接受 / 拒绝 结果 , 因此 每个计算分支都是有限长的 ; 无限长的分支说明进入了 Loop 循环状态 ;

非确定性图灵机 计算树 参考 【计算理论】图灵机 ( 非确定性图灵机 | 非确定性图灵机指令分析 | 计算过程 | 非确定性指令出现多个分支 | 非确定性图灵机转为计算树 | 计算树 ) 博客 ;

非确定性图灵机 时间复杂度是一个函数 , 该函数是从 自然数 到 自然数 映射的一个函数 ,

记做 :

\rm f(n) : N \to N

, 函数的定义域值域都是 自然数

\rm N

;

定义域 : 定义域中的自然数

\rm N

表示 输入字符串的大小 ,

值域 : 值域中的自然数

\rm N

表示 计算步数 ;

确定性图灵机 计算 , 与 非确定性图灵机 计算 的差别 :

确定性图灵机 在字符串上进行计算时 , 只有一个分支 , 非确定性图灵机 在字符串上进行计算时 , 有很多个分支 ;

非确定性图灵机 时间复杂度取值 : 将所有的长度为

\rm n

的字符串 , 依次输入到 非确定性图灵机 中进行计算 , 得到的计算树是不同的 , 所有的计算树中 , 高度最高的计算树的高度 , 作为计算的步数 , 也就是时间复杂度的取值 ;

二、非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的指数关系

---

使用 确定性图灵机 , 模仿 非确定性图灵机 , 在 计算效率方面要付出一定的代价 , 计算复杂度会 指数级增加 ;

如果 非确定性 单个带子 图灵机 , 时间复杂度是

\rm O(t(n))

,

找到一个 等价的 确定性 单个带子 图灵机 , 其时间复杂度是

\rm 2^{O(t(n))}

;