如何看待科学网发布文章称「我国数学家证明 NP=P」，是真的吗？如果是，会带来怎样的影响? 第1页

如何看待这件事? Not even wrong.

P=NP 可以完全推翻一系列领域的理论基础, 包括但不限于公钥密码学 (包括主流后量子密码), 量子计算优越性 (如 Google 的随机线路采样), 比特币验证依赖的 succinct argument 和零知识证明. 如果觉得自己有能力解决 P 和 NP 的关系的话, 建议先考虑最后一节我列出来的较为容易的公开问题.

Gerhard J Woeginger 在去 RWTH Aachen 之前, 曾经维护了一个关于 P 和 NP 关系的各种"伪证" (喜好用词"尝试"的各位自便) 的页面 (一直更新到了 2016 年):

想咬文嚼字说这个列表里不全是"伪证"的, 请移步下一节. 通过简单的搜索不难发现第 53 条如下:

53. [Equal]:In April 2009, Xinwen Jiang published a proof for P is equal to NP. He provided an algorithm for the Hamilton circuit problem, and states"It seems our algorithm is a polynomial one".The paper can be found athttp://xinwenjiang.googlepages.com/. An earlier version of his paper was published in a Chinese journal in 2007.
Further versions have been published in 2010 and 2011. More information on the current version of the proof is available athttp://trytoprovenpvsp.blog.sohu.com/entry/.
Since May 2013, the paper"A Polynomial Time Algorithm for the Hamilton Circuit Problem"is available athttp://arxiv.org/abs/1305.5976.
(Thanks to Maris Ozols for providing some of these links.)

有兴趣查证各种链接的同学, 可以结合 https://archive.org/web/ 来考证相关的历史链接.

有人非要跟我质疑说那个链接收集的是 P-versus-NP 的"尝试"列表, Yannakakis 的文章就不是"伪证"云云. 这些条目里被学术界讨论过应该只有 natural proof (和 circuit complexity 有关, 我并不熟悉) 相关的, 还有前两年 Norbert Blum 的证明 (如 Luca Trevisan 的博文 中的讨论).

自己看好了第一条是怎么写的, 主角是 Ted Swart:

[Equal]: In 1986/87 Ted Swart (University of Guelph) wrote a number of papers (some of them had the title: "P=NP") that gave linear programming formulations of polynomial size for the Hamiltonian cycle problem. Since linear programming is polynomially solvable and Hamiltonian cycle is NP-hard, Swart deduced that P=NP. In 1988, Mihalis Yannakakis closed the discussion with his paper "Expressing combinatorial optimization problems by linear programs" (Proceedings of STOC 1988, pp. 223-228). Yannakakis proved that expressing the traveling salesman problem by a symmetric linear program (as in Swart's approach) requires exponential size. The journal version of this paper has been published in Journal of Computer and System Sciences 43, 1991, pp. 441-466.

Yannakakis 的工作单独成项了吗? 是 Yannakakis 证明是关于 P 和 NP 关系的尝试吗?

这一项主要内容是 Ted Swart 一系列通过把 Hamiltonian cycle problem 写成多项式规模的对称线性规划的尝试, 这是那一条的主要内容. "对称"是说线性规划的对偶的对偶就是原来的线性规划. 其后的讨论是 Mihalis Yannakakis 终于证明了这一问题不能写成对称线性规划, 因为证明了下界是指数的. 当然不是所有关于 P 和 NP 关系的错误证明都能导出有意义的问题.

后来仍然有一些人锲而不舍的写出某些 NP 完全问题的非对称形式的多项式规模线性规划, 譬如说:

37. [Equal]: In December 2006, Howard Kleiman proved that P is equal to NP: http://arxiv.org/abs/math.CO/0612114. The title of the paper is "The Asymmetric Traveling Salesman Problem". Kleiman uses a modification of the Floyd-Warshall algorithm to solve the Asymmetric Traveling Salesman Problem in polynomial time.
66. [Equal]:In August 2010, Sergey Gubin proved that the ATSP (Asymmetric Travelling Salesman Polytope) can be expressed by an asymmetric linear program of polynomial size. This implies P=NP. His paper"Complementary to Yannakakis' theorem"has been published in Volume 74 of The Journal of Combinatorial Mathematics and Combinatorial Computing on pages 313-321. And here is a refutation of Gubin's arguments by Romeo Rizzi from January 2011.

直到 2012 年 Ronald de Wolf 等人证出来的 extension complexity 指数下界 (STOC 2012 最佳论文奖), 再次终结了这一类"尝试". 对进一步的细节感兴趣的欢迎阅读我的回答:

我也不是很理解为什么要讨论这种 not even wrong 的东西. 但是很迷的是, 看楼下的博客链接, 这一系列结果竟然还拿到了2012 年 NSFC 的资助? 引自该作者的新浪博客《哈密顿图判定问题的多项式时间算法》发表:

好在全部工作获得国家自然科学基金（NP完全问题求解复杂性研究，61272010）等项目的支持。

比起直接证明 P 和 NP 的关系, 建议考虑证明或推翻以下较为容易的问题:

• 证明 P 不等于 PSPACE;
• 给出 Learning with Error 问题的经典或量子多项式时间算法;
• 证明 AM=MA, 如果觉得太容易的话, 可以考虑证明 P=BPP;
• 证明 QCMA = QMA, 或 QCMA = QMA(2), 或者里面随便挑两个证明相等;
• 证明 NL=L 或 BPL=L;
• 证明 BQP=QPIP.

哦忘记说了, 第二项是 P=NP 的推论. 因为 LWE 的 hardness 证明依赖的 poly-approximated GapSVP 是在 NP cap coNP 里的, 所以能导出 LWE 的经典多项式时间算法. 作为脚注, Oded Regev 曾在某次报告中表示,

“每年都有几天, 我早上醒来, 会收到邮件声称给出了某些格问题 (lattice problems) 的多项式时间的算法”.

如果有人能给出 LWE 的 (量子) 多项式时间算法的话, 我会非常高兴, 因为我个人很不喜欢现在 LWE-based quantum delegation 的这些结果.

最容易证明的可能是第五项, 今年 STOC 的 workshop 上有几个大佬表示基于近年的一系列进展, 有望在十年内证明 BPL=L -- 目前最好的上界是二十多年前 Saks-Zhou 的 BPL is in L^{3/2}. 剩下最容易的可能是第三项, 但是现在甚至没有比 P=BPP 更弱的备选前提条件. 第四项和第六项目前没有任何头绪, 第六项也有一些人认为不成立.