【小知识】存在NTM明确快于DTM的复杂性类吗

今天的计算理论课上，老师在讲NFA（非确定型有限自动机），然后就顺嘴提了一下以后要讲的NTM（非确定型图灵机）和DTM。他问：“NTM和DTM的计算能力一样吗？”（他指的是判定语言的能力）答案显然是一样的。他又问：“NTM和DTM的计算效率一样吗？”我脱口而出不一样，NTM更快。但又犹豫了。

老师说：“这个问题目前还不清楚，这就是P vs NP问题。”

I mean, hold on…

一个更强的问题

我马上意识到，尽管老师只是想引出，但他前述的问题（“NTM和DTM的计算效率一样吗”）事实上指称了一个更强的问题——是否存在NTM明确快于DTM的复杂性类？

由于线性加速定理，系数上的区别显然是无关紧要的。

我的脑子里一时没有答案。

一个不一定正确的回答

在一则相关的Quora问答里，有人给出了一个答案，称确定性图灵机下排序的时间复杂度不会快于，而非确定型图灵机下排序可以不差于。

然而，评论里有人指出，首先，这里的是待排序的项目数，而这意味着信息量（至少是），这是因为当项目数变多时，我们必须使用更多的bit数才能唯一的表示这些项目。那么，按照传统计算理论的设置，我们应该令。在这个意义上，评论区老哥经过分析指出，确定型图灵机只需要关于近线性的时间复杂度。然而我们不一定要把算法控制在比较算法里，因此或许可能有更低的时间复杂度？（桶排序之类的算法假设了很多东西，不能算general意义下的线性）

这一点不是很清楚。我们暂且搁置。

更多的答案

我于是去搜索complexity zoo。

我发现了这样一个定理：

但是的定义过于复杂（其实只是我这个懒狗不想去看原始文献了），所以我也不知道这个究竟是否符合要求。

然后我在Quora里提了个问题：

Is non-deterministic turing machine strictly better than deterministic turing machine in some cases? - Quora

收到了一些精彩的（精彩并不意味着正确！）回答，选择两则：

一个简洁的构造性答案。

NTM可以做到是毫无疑问的，但是答主在这里对DTM的算法有些含糊。对，我们可以理解DTM不得不来回扫，这会比较糟糕，但究竟怎么个糟糕法？最好算法是什么？

想到这的时候我发现这个答案可能是错误的。因为时间复杂度首先是关于信息长度的，那么此时就代表那个特殊字符与原点之间的距离。如果是可知的，扫描整个字符串不是一件很容易的事吗？

于是我回复他：

他后来基本承认了这个问题事实上只有常数级别的gap，但是我们已经说过了，常数gap算不上gap。

不过这个“错误”仍然有很值得讨论的东西，我们后面再开篇博客讲。

还有一个学术性的答案：

这个答案真正理解了我在说什么，而且以一个肯定的回答完美地解决了。

STOC’84上的一篇老文

Quadratic lower bounds for deterministic and nondeterministic one-tape turing machines

给出了下述定理：

这也就是说，一定存在这样的问题，它能在线性时间内被解决，但需要至少的时间才能由解决。

文章同时构造性地给出了这样的一个问题。

但是，还有没有什么“自然的问题”可以作为实例呢？这对我以及这位答主来讲仍然是Open的，因为就像他说的：

One obstacle is that our lower bounds for deterministic machines are really, really poor.