文章目录
证明 非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的指数关系
证明 非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的指数关系
在上一篇博客 【计算理论】计算复杂性 ( 非确定性图灵机的时间复杂度 | 非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的关系 ) 中 , 提出如下命题 :
使用 确定性图灵机 , 模仿 非确定性图灵机 , 在 计算效率方面要付出一定的代价 , 计算复杂度会 指数级增加 ;
如果 非确定性 单个带子 图灵机 , 时间复杂度是 O ( t ( n ) ) \rm O(t(n))O(t(n)) ,
找到一个 等价的 确定性 单个带子 图灵机 , 其时间复杂度是 2 O ( t ( n ) ) \rm 2^{O(t(n))}2
O(t(n))
;
证明上述命题 :
给定 非确定性图灵机 , 找到一个确定性图灵机 , 模仿该 非确定图灵机 , 实际上是沿着 非确定性图灵机 计算树 最长的分支 , 进行模仿 ;
如何找到 计算树 的最长分支呢 , 即 沿着 计算树 进行 宽度优先搜索 :
假设计算树的高度是 f ( n ) \rm f(n)f(n) , 该计算树在最坏的情况下 , 要走的步数 , 主要决定于 树的节点个数 ,
如果 计算树 的高度是 f ( n ) \rm f(n)f(n) , 计算树的节点个数的数量级是 2 f ( n ) \rm 2^{f(n)}2
f(n)
数量级 ; ( 计算二叉树的节点 , 最坏的情况下就是满二叉树的节点个数 )
确定性图灵机 与 非确定性图灵机 计算相同的问题 , 计算的时间 满足如下关系 :
如果 非确定性图灵机 所花费的时间是 t ( n ) \rm t(n)t(n) ,
则 确定性图灵机 所花费的时间是 2 t ( n ) \rm 2^{t(n)}2
t(n)
;
