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

文章目录

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

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

---

在上一篇博客 【计算理论】计算复杂性 ( 非确定性图灵机的时间复杂度 | 非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的关系 ) 中 , 提出如下命题 :

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

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

\rm O(t(n))

,

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

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

;

证明上述命题 :

给定 非确定性图灵机 , 找到一个确定性图灵机 , 模仿该 非确定图灵机 , 实际上是沿着 非确定性图灵机 计算树 最长的分支 , 进行模仿 ;

如何找到 计算树 的最长分支呢 , 即 沿着 计算树 进行 宽度优先搜索 :

假设计算树的高度是

\rm f(n)

, 该计算树在最坏的情况下 , 要走的步数 , 主要决定于 树的节点个数 ,

如果 计算树 的高度是

\rm f(n)

, 计算树的节点个数的数量级是

\rm 2^{f(n)}

数量级 ; ( 计算二叉树的节点 , 最坏的情况下就是满二叉树的节点个数 )

确定性图灵机 与 非确定性图灵机 计算相同的问题 , 计算的时间 满足如下关系 :

如果 非确定性图灵机 所花费的时间是

\rm t(n)

,

则 确定性图灵机 所花费的时间是

\rm 2^{t(n)}

;