CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

科研需要坚韧不拔的意志和无所畏惧的精神

已有 4215 次阅读 2017-5-1 22:20 |个人分类:3SAT解法|系统分类:科研笔记| 子句消去法, 3-SAT

 

姜咏江

有一段时间没写博文了,原因很简单,忙着将子句消去法写成计算机程序。说实在的,对一个七十多岁的人来说,还真是有点玩命。但我这个人办事不愿意半途而废。今天是“五一”劳动节,我确实还真地劳动了一番,将求3-SAT满足解的程序彻底完成了。高兴之余,想起来写点,以作为纪念。

为什么要拼命自己编程?很简单,别人编不来。我说我解决了SAT问题的多项式时间算法,大概没有什么人会相信,因为中涉及到了P/NP这个几十年未能够解决的计算机科学的世界难题,世界上那么多聪明的科学家,数学界、计算机界的名人名家都未能解决,你就解决了?其实,这是一般人的习惯看法。但事情总有特殊性,我就是那种特殊的人物。

SAT问题的全解和满足解问题,我都在理论上解决了。可是要学界的人们认可你,那可不是一件容易的事情。特别是在我们中国,就更是困难。原因是一般学者说了不算,而权威名家一般都不会轻易说出自己的见解,P/NP问题毕竟是全世界都一直未能解决的头号难题。为了让学术界认可,需要做艰苦细致地工作,其中最重要的是拿出“真东西”来!真东西是什么?就是实际能够求SAT满足解的程序。说起来,这就是我非要玩命设计出求解SAT 解问题程序的根本原因。

我说过,子句消去法求3-SAT的满足解时间复杂度不超过O(n4),通过我写出的程序执行,完全可以证实这个结论。上百个变量的3-SAT求解,在我的笔记本上十几秒就可以得到结果。顺便说一句,那种用随机的方法产生的合取范式,能否得到正确的解,同样具有随机性。因而在理论上说明不了什么。本人的子句消去法可以清楚地告诉人们,什么情况下SAT有解,什么情况下无解,而且会准确地说出解的数量。国外搞得SAT竞赛,据说每年一次。这种竞赛在没有理论保证的情况下,应该说只是一种游戏而已。如果他们能够认识到我创造的理论的正确性,这种游戏就该结束了。从这方面看,我的研究倒有点罪过了。。。

SAT问题的解决,据说涉及众多方面,但我感到最重要直接的是集成电路优化、可靠性检测,这涉及到信息产品的效率、速度、可靠性、安全性。未来设计的超大规模集成电路系统,不会发生未知原因的死机,也不用设计那种“看门狗”之类的东西。如果集成电路运行状态都在我们的掌控之中,在相互比拼的决战中,不出状况,岂不是会高人一头?用在国防战场方面,意义之重大可想而知!

不怕讽刺挖苦,科研需要有坚韧不拔的精神,成功就属于你。当然,这一切需要你有雄厚的根基,渊博的知识和勇于探索的底气。

为了纪念我实际设计求解3-SAT满足解和全解的程序的完工和测试,特此写字。

2017-5-1

 

 

 



https://wap.sciencenet.cn/blog-340399-1052316.html

上一篇:二进制数纠缠态与SAT问题全解
下一篇:征求数字电路优化和基因计算等方面合作者
收藏 IP: 118.144.20.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

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

GMT+8, 2024-3-28 19:34

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部