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