我发现以下声明:
如果非确定性图灵机的程序 P 在时间上解决由多项式 p(S) 限制的决策问题，其中输入的大小为 S，那么它可以在确定性图灵机上运行，并且解决方案将是在时间有限的时间内找到 O(2^p(S))。
我的问题是这个说法是否正确，我们如何证明它？确切的值 2 在这里是可疑的。
最佳答案
确定性图灵机只是模拟非确定性图灵机。每次 NDTM 获取 fork 时，DTM 都会推送一个分支并获取另一个分支。当它遵循一个可能的链 p(S) 个步骤而没有达到接受状态时，它回溯到前一个分支点。
这假设 NTDM 仅执行双向分支。如果它最多可以占用 k 个分支，请将其重写为仅执行双向分支的机器，将其运行时间增加到 O(log_2(k) p(S))，这使得它在技术上仍然是 O(p(S) )。这里有一点马虎。如果 x > 1，O(2^{x p(S)} 大于 O(2^{p(S)})，因此虽然我们可以忽略与完整表达式相乘的常量因子，但我们不能在指数中忽略它们.
关于complexity-theory - 程序在确定性和非确定性图灵机上的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28245305/