象一棵树,栽在溪水旁分享 http://blog.sciencenet.cn/u/Furaibo 你要专心仰赖耶和华,不可依靠自己的聪明

博文

P对NP -- 与杨正瓴老师商榷

已有 4146 次阅读 2012-3-24 18:01 |个人分类:书斋小记|系统分类:论文交流

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

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

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

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

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

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



http://blog.sciencenet.cn/blog-66861-551309.html

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

6 杨正瓴 钟炳 庄世宇 黎夏 陈湘明 刘钢

发表评论 评论 (22 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-9-30 05:21

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部