|||
姜咏江
今天得闲,浏览了ECCC网站,好像是以色列主办的,过去没接触过。浏览2017年的文章,首先被ScottAaronson教授的P ? = NP一文所吸引。文章太长,总而言之是P/NP问题很难,很重要等,没见到问题已经解决的字样。
数学证明具有很强的逻辑性,但基础是概念和事实。文中提到尚未见到多项式时间的算法出现,因而难说P与NP是否相等。我所做的工作正是找到了SAT problem这个NP-complete问题的多项式时间算法,因而我想Scott Aaronson的文章落后了。
P/NP问题很多人走的是企图用旧有的概念和方法去证明两者之间的关系,失败的原因就是没有见到一个NP-complete问题的多项式时间算法,又不能肯定这种算法是否存在,也就是缺乏事实依据,缺乏应有的概念,故而没法用逻辑来推导出确定正确的结论。
多见证明文章冗长,几乎都成了一本书,早就失去了数学证明的特色,难免出现逻辑或概念上的偏差,也不易被人完全读懂,自然让人们认可起来也相当困难。这大概是P/NP问题证明的盲点。
我所追求的是具体的SAT问题算法,以子句消去法这个算法去探讨多项式时间复杂度,进而踩在库克的肩膀上,去说明了P=NP罢了。
子句消去法可以在多项式时间内求出SAT的满足解,前文已经提到。昨天又将《 All Solutions of SAT by Eliminate Clause and Its Possible Solutions Method》一文放到了arXiv.org网站上,编号1823386。之前还放上了《Clause Elimination Method for Vertex Cover》,编号1791707;《Solve the Maximum Clique by the New Data Structure》,编号1791794。毫无疑问,运用文中介绍的算法都可以证明在多项式时间将需要的解求出来。
这些论文都以介绍实际算法为主,进而依据算法的实际来证明这几个NP-complete问题,都可以针对最坏的情况,在多项式时间获得解答。因为我实实在在地给出了前所未有的算法,因而我有充分的底气,敢说P=NP。
Scott Aaronson教授什么时候能够见到我的子句消去法和以上的论文,或许会惊讶。也许这几篇论文不太English,我猜他也会理解我的算法,也会写出新的论题。
事实是概念的基础,正确概念是论证的基石。
2017-2-18
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-27 11:13
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社