重大喜讯，放军教授成功解决世界第一难题P=NP (转载)# JobHunting - 待字闺中
n*6
1 楼
【 以下文字转载自 Military 讨论区 】
发信人: WangMaZi (王二小), 信区: Military
标 题: 重大喜讯，放军教授成功解决世界第一难题P=NP
发信站: BBS 未名空间站 (Thu May 19 00:05:54 2016, 美东)
国防科大教授姜新文微博
http://blog.sina.com.cn/s/blog_54de27b80102vgyf.html
5年前我们正式投稿推出一个32页文章，讲述为一个图论问题设计的算法。文章
内容属于算法设计与分析的范畴，文章结构遵循算法设计与分析教科书中提出问题、设
计算法、分析证明的俗套，采用的方法、技术、手法都来自基本的教科书。理解文章需
要的知识背景被计算机、数学、信息安全等本科专业覆盖。但是因为明确指出了该算法
是一个NP完全问题的多项式算法，所以，如果算法对了，NP就等于P了。这意味着同时
具备重大理论意义和现实意义的世界第一困难问题被解决，意味着人类认识世界的自动
化过程现实可行，意味着非确定性变成确定性，意味着密码学崩溃和密码学可能成为皇
帝新装，意味着哲学上支持世界可知。于是一个接受世界质询的过程开始了。
回顾过去5年接受质询的过程，必须首先向5年中给我们的工作予以关心、指导
、帮助、质询、匡正，特别是花费大量时间和精力逐字阅读、推敲、研讨、验证的所有
国内外专家、教授、科学家，以及中南大学、北航大学、北京大学、香港理工、国防科
大（还有2所大学听说有研讨）的一些优秀学生，表示衷心感谢和致敬！
5年中，我们和国内外许多计算机科学家和数学家进行了多次的、反复的从1天
，到2、3天，到4、5天，到一周的集中研讨，也在国内顶尖大学按课程形式开展了为期
数月的、每周两次每次2小时的研讨。还分别到2所大学以及中科院进行了为期一月的访
问。5年中我们回答了约50封关于文章内容的、必须回答的提问邮件，参加了否定NP≠P
的审稿并因快速和精准获高度赞扬。5年中我们尽力完成了5300万例随机测试和几万例
指定测试。5年中，我们发表了10多个关于我们提出的MSP问题的NP完全性证明，以回答
MSP问题是否NP完全问题的质疑。（顺便报告一下，5年以前，当我们不说MSP问题是NP
完全问题，只说有这么个问题有这么个算法时，很多审稿意见充分肯定算法正确，否定
文章意义。）
现在，5年过去，没有结论没有发现重要错误。我希望同时也感觉是开辟第二战
场甚至第三战场打响决定性战斗的时候了。
首先，这个决定性战斗值得打响啊！
搜索“P vs NP”、“NP完全问题”等关键词，可得到该问题以及意义的大量描
述。解决这样的问题，是人类认识世界的重要进步。在大学研教三十年，我没有其他学
者具备的做大事的能力，也不能像同事们那样作为主力参加天河工程将夺取世界第一做
成习惯，为国争光，个人只是像一颗螺丝钉将自己牢牢钉在一个大系统中，守住自己的
职责，默默做着研究和教学的工作。值得庆幸、必须感谢的是，研究得到包括国家自然
科学基金在内的多方连续资助。如果文章正确，那是每年投入几千亿开展科学研究的中
华大地上长出的一颗小草，是众多学者鼓励支持帮助的结果，是中国梦驱动民族复兴、
科学复兴的滚滚洪流中的一朵能量非负的浪花。
其次，总攻时机已到，是各路大神出手定乾坤的时候了。
（1）5年来的反复磨练，使我们进一步将论文由原来的32页，简化成现在的10
页。忽略掉那个问题是NP完全问题一句话，文章完全属于最基本的算法设计与分析范畴
。除搞硬件的人外，算法设计属于计算机、数学、密码学等类专业的基本功。如果说在
32页论文中查找错误是大海捞针，现在或许算瓮中捉鳖了。
（2）计算机、数学、密码学等等领域，与算法相关的工作，回到计算的本质，
很多割不断与我的文章的联系和比较。每年几千个亿研究经费的一部分，被投入到各种
与算法和计算复杂性相关的研究，每个项目都是几十万几百万，如果我的文章对了，很
多研究或许就不要做了，可以省下钱来派做百姓安居、治病救人、保家卫国的百端用场
啊。
（3）我们总是被导师和大腕鼓励，要有不畏艰难的创新精神，要有敢于挑战的
勇气。另一方面，我们也总是被人们提醒，怎么打开书本很少中国学者贡献的知识，怎
么原创性研究很少。其实，我的工作就是一件原创性工作。来自反复推敲论文和反复与
人研讨请教的信心告诉我，NP=P是肯定的，任何NP不等于P的证明必然包含错误。但是
，如果我们总是不决，这件事可能最后将变成外国人最先发表。
（4）是的，如果错了怎么办？确实很难事先绝对看准事情。看准的学术带头人
还有不走学术路而走造假和贪污腐败路的。审定论文需要阅读，还可能需要报告和讨论
。耗费您的时间，我无以为报，只能永远地心怀感激了！就当捐给希望工程几个志愿工
作日吧。毕竟，个人的研究做到这个地步，有科学家跟我说过，已经不仅仅属于个人的
追求。
再次，生命的急迫感也使我感受决定性战斗的必要性。
本来多少年慢慢等待，也还心静如止水。2014年底，忠实执行工作任务过程中
的一个偶然事件，使我严重损失听力，住院很长时间才开始慢慢恢复过程，至今还觉艰
难，与人交往、交流的方式被迫开始改变。躺在病床上的时候，在无声的世界里，我不
免感概生命。风树流年，人的生命都在慢慢老去，螺丝钉也开始慢慢生锈，以后我也会
慢慢脑力下降。很久以后，如果需要，我还能说清楚曾经的认识吗？
各路大神显灵吧！朋友们一起关注一起帮助吧！为了很多的为了，为了共同的为了，帮
审定、帮组织、帮推动、帮呼吁、帮传递呼吁！
（10页文章链接（借用中国科学版式）
http://wenku.baidu.com/view/b733df30c850ad02df804108?qq-pf-to=pcqq.c2c 。
5年前的32页论文 http://arxiv.org/ftp/arxiv/papers/1305/1305.5976.pdf
关于第二战场第三战场的涵义，在本博文征求意见阶段，我就被问到。除了新的10页版
本的并行的新投稿，还没有其它主意。我在[email protected]/* */ 或者微信 nudt_
xinwen 乞等支招和帮助。）
发信人: WangMaZi (王二小), 信区: Military
标 题: 重大喜讯，放军教授成功解决世界第一难题P=NP
发信站: BBS 未名空间站 (Thu May 19 00:05:54 2016, 美东)
国防科大教授姜新文微博
http://blog.sina.com.cn/s/blog_54de27b80102vgyf.html
5年前我们正式投稿推出一个32页文章，讲述为一个图论问题设计的算法。文章
内容属于算法设计与分析的范畴，文章结构遵循算法设计与分析教科书中提出问题、设
计算法、分析证明的俗套，采用的方法、技术、手法都来自基本的教科书。理解文章需
要的知识背景被计算机、数学、信息安全等本科专业覆盖。但是因为明确指出了该算法
是一个NP完全问题的多项式算法，所以，如果算法对了，NP就等于P了。这意味着同时
具备重大理论意义和现实意义的世界第一困难问题被解决，意味着人类认识世界的自动
化过程现实可行，意味着非确定性变成确定性，意味着密码学崩溃和密码学可能成为皇
帝新装，意味着哲学上支持世界可知。于是一个接受世界质询的过程开始了。
回顾过去5年接受质询的过程，必须首先向5年中给我们的工作予以关心、指导
、帮助、质询、匡正，特别是花费大量时间和精力逐字阅读、推敲、研讨、验证的所有
国内外专家、教授、科学家，以及中南大学、北航大学、北京大学、香港理工、国防科
大（还有2所大学听说有研讨）的一些优秀学生，表示衷心感谢和致敬！
5年中，我们和国内外许多计算机科学家和数学家进行了多次的、反复的从1天
，到2、3天，到4、5天，到一周的集中研讨，也在国内顶尖大学按课程形式开展了为期
数月的、每周两次每次2小时的研讨。还分别到2所大学以及中科院进行了为期一月的访
问。5年中我们回答了约50封关于文章内容的、必须回答的提问邮件，参加了否定NP≠P
的审稿并因快速和精准获高度赞扬。5年中我们尽力完成了5300万例随机测试和几万例
指定测试。5年中，我们发表了10多个关于我们提出的MSP问题的NP完全性证明，以回答
MSP问题是否NP完全问题的质疑。（顺便报告一下，5年以前，当我们不说MSP问题是NP
完全问题，只说有这么个问题有这么个算法时，很多审稿意见充分肯定算法正确，否定
文章意义。）
现在，5年过去，没有结论没有发现重要错误。我希望同时也感觉是开辟第二战
场甚至第三战场打响决定性战斗的时候了。
首先，这个决定性战斗值得打响啊！
搜索“P vs NP”、“NP完全问题”等关键词，可得到该问题以及意义的大量描
述。解决这样的问题，是人类认识世界的重要进步。在大学研教三十年，我没有其他学
者具备的做大事的能力，也不能像同事们那样作为主力参加天河工程将夺取世界第一做
成习惯，为国争光，个人只是像一颗螺丝钉将自己牢牢钉在一个大系统中，守住自己的
职责，默默做着研究和教学的工作。值得庆幸、必须感谢的是，研究得到包括国家自然
科学基金在内的多方连续资助。如果文章正确，那是每年投入几千亿开展科学研究的中
华大地上长出的一颗小草，是众多学者鼓励支持帮助的结果，是中国梦驱动民族复兴、
科学复兴的滚滚洪流中的一朵能量非负的浪花。
其次，总攻时机已到，是各路大神出手定乾坤的时候了。
（1）5年来的反复磨练，使我们进一步将论文由原来的32页，简化成现在的10
页。忽略掉那个问题是NP完全问题一句话，文章完全属于最基本的算法设计与分析范畴
。除搞硬件的人外，算法设计属于计算机、数学、密码学等类专业的基本功。如果说在
32页论文中查找错误是大海捞针，现在或许算瓮中捉鳖了。
（2）计算机、数学、密码学等等领域，与算法相关的工作，回到计算的本质，
很多割不断与我的文章的联系和比较。每年几千个亿研究经费的一部分，被投入到各种
与算法和计算复杂性相关的研究，每个项目都是几十万几百万，如果我的文章对了，很
多研究或许就不要做了，可以省下钱来派做百姓安居、治病救人、保家卫国的百端用场
啊。
（3）我们总是被导师和大腕鼓励，要有不畏艰难的创新精神，要有敢于挑战的
勇气。另一方面，我们也总是被人们提醒，怎么打开书本很少中国学者贡献的知识，怎
么原创性研究很少。其实，我的工作就是一件原创性工作。来自反复推敲论文和反复与
人研讨请教的信心告诉我，NP=P是肯定的，任何NP不等于P的证明必然包含错误。但是
，如果我们总是不决，这件事可能最后将变成外国人最先发表。
（4）是的，如果错了怎么办？确实很难事先绝对看准事情。看准的学术带头人
还有不走学术路而走造假和贪污腐败路的。审定论文需要阅读，还可能需要报告和讨论
。耗费您的时间，我无以为报，只能永远地心怀感激了！就当捐给希望工程几个志愿工
作日吧。毕竟，个人的研究做到这个地步，有科学家跟我说过，已经不仅仅属于个人的
追求。
再次，生命的急迫感也使我感受决定性战斗的必要性。
本来多少年慢慢等待，也还心静如止水。2014年底，忠实执行工作任务过程中
的一个偶然事件，使我严重损失听力，住院很长时间才开始慢慢恢复过程，至今还觉艰
难，与人交往、交流的方式被迫开始改变。躺在病床上的时候，在无声的世界里，我不
免感概生命。风树流年，人的生命都在慢慢老去，螺丝钉也开始慢慢生锈，以后我也会
慢慢脑力下降。很久以后，如果需要，我还能说清楚曾经的认识吗？
各路大神显灵吧！朋友们一起关注一起帮助吧！为了很多的为了，为了共同的为了，帮
审定、帮组织、帮推动、帮呼吁、帮传递呼吁！
（10页文章链接（借用中国科学版式）
http://wenku.baidu.com/view/b733df30c850ad02df804108?qq-pf-to=pcqq.c2c 。
5年前的32页论文 http://arxiv.org/ftp/arxiv/papers/1305/1305.5976.pdf
关于第二战场第三战场的涵义，在本博文征求意见阶段，我就被问到。除了新的10页版
本的并行的新投稿，还没有其它主意。我在[email protected]/* */ 或者微信 nudt_
xinwen 乞等支招和帮助。）