杨正瓴老师在我的博文后留言，让我评论一下他的《[请教] P对NP：请郝克刚教授等专家指教（一）》。其实，我们在春节期间就有过一些邮件交流。由于已经好多年不做这方面的研究了，一直没有勇气去深入思考杨老师提出的有意思的想法。今天下午，又仔细读了杨老师的博文，发现杨老师关于无穷化版本下的“P对NP”问题的描述可能是有问题的。我对集合论研究不深，特别是谈到可数无穷基数时，更是常常犯迷糊，所以也可能是我理解错误。我的理解如下，请杨老师和其他同仁指正。

(1)称一个问题A是DTM多项式时间可解的，是指存在一个算法(DTM)，对于问题A的任意长度为n的输入（该问题的一个测试用例，n是一个有穷自然数），算法最多执行（n^k）步，其中k是一个常数。这样的所有问题所对应的问题类是P类。

(2)称一个问题A是DTM多项式空间可解的，是指存在一个算法(DTM)，对于问题A的任意长度为n的输入（该问题的一个测试用例，n是一个有穷自然数），算法在执行过程中所使用的空间最多不会超过n^k，其中k是一个常数。这样的所有问题所对应的问题类是PSPACE类。PSPACE类包含NP类，但是包含在EXPTIME类中。

(3)对于PSPACE类中的任意问题，均存在一个DTM，最多使用n^k的空间，求解该问题。由于DTM的有穷控制器的状态是有限的，字母表是有限的，而所使用的空间也是有限的 (有穷自然数的多项式)，从而由这三者所构成的图灵机的所有可能的内部状态也是有限的。虽然在计算的过程中，可能会重新回到某个内部状态，但该图灵机总会在有限步停机的。

我觉得，杨老师可能混淆了“能够解决NP类问题的NDTM” 和“所有的NDTM”，或者混淆了问题和问题的测试用例（或者说混淆了形式语言中的“语言”和“语言中的一个字符串”）。

一个语言中的字符串可能是无穷可数的，但是一旦拿出一个字符串来，交给图灵机去判断这个字符串是否属于这个语言时，这个字符串就是有限长度的。也就是说，算法的每次执行（一个进程），其状态总是有限的。所以，我认为，对于P类和NP类问题，不应该有将DTM、NDTM的运行时间取为无穷大（可数无穷步）之说。

转载本文请联系原作者获取授权，同时请注明本文来自徐建良科学网博客。
链接地址：https://blog.sciencenet.cn/blog-66861-551309.html

上一篇：我的自白书 -- 送给湘明兄的诗是偷来的
下一篇：校园樱花