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