下面是通过求解哈密顿图问题有多项式时间算法而证明20世纪世界排名第一的数学家提出的千禧年难题NP=P的中国学者的论文：

1、武汉科技大学计算机科学与技术学院杜立智教授（1964年生，上海交通大学学士，纽约州立大学硕士。在美国等软件公司从事软件开发工作多年）：这是他的证明论文。

2、桂林电子科技大学朱国魂教授（2005 年7月至2006年7月日本东京工业大学担任客员研究员，是“无所不在网络的图论应用国际会议”主席），这是他的证明论文。

3、浙江师范大学经济与管理学院副院长段文奇教授（他的硕士学位、博士学位论文都做网络相关课题。如2008年出版182页的《网络市场环境…》，2010年和美国科学院院士H. Eugene Stanley合作这里的第146、163篇论文），这是他的证明论文。

附：美国克雷数学研究所发布的每个问题奖百万美元的千禧年难题Millennium Problems的上面问题（不仅是下面千禧年第3个数学问题，还更是计算机的世界第一问题）：

P vs NP Problem

If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This is the essence of the P vs NP question.

Typical of the NP problems is that of the Hamiltonian Path Problem: given N cities to visit, how can one do this without visiting a city twice? If

you give me a solution, I can easily check that it is correct. But I cannot so easily find a solution.

（这上面3行字意思是“如果容易核对一个解是正确，是否也容易解决这问题？这是P对NP问题的实质。NP问题的最优代表是哈密顿路问题：给N个城市去全都访问，如何做这访问以便任何城市都不访问2次？如果你给一解答，我能容易核对它的正确性。但我不能如此容易发现一解答”）

可参考Stephen Cook 的The Importance of the P versus NP Question, Stephen Cook. JACM 50, 1, 2003；

Michael Sipser 的The History and Status of the P versus NP Question；STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

Michael Sipser的博士Lance Fortnow 最近的The status of the P versus NP problem. Commun. ACM 52, 9 (Sept. 2009), 78–86；

Eric Allender的A Status Report on the P Versus NP Question，Advances in Computers Volume 77, 2009, Pages 117-147；

Scott Joel Aaronson的P = ? NP以及Is P versus NP formally independent；

图灵奖得主Adi Shamir的博士Uriel Feige的The P versus NP question: is there any progress或见；

Oded Goldreich的P, NP, and NP-Completeness: The P versus NP Question；

Stasys Jukna的On the P versus NP intersected with co-NP question in communication complexity

其中的“给N个城市去全都访问，如何做这访问以便任何城市都不访问2次？”，若以点表示城市，这是N个点的哈密顿路的定义。若没有访问2次并回到出发城市，是哈密顿圈的定义，此图叫哈密顿图（这里有很多哈密顿图判定构造等的技术途径方法成果理论…）。

部分爱好者是看到上面如此简单的三行字的描述而且解决每个问题奖百万美元如此某些没有丰富、长久、深入的哈密顿图以及计算复杂性理论等研究经历的人也研究之（有些甚至对确定型和非确定型图灵机、各类NP理论、多项式时间归约等基本的概念和理论都没有很好掌握甚至没有听说过的人也研究）。其实，要掌握处理NP完全问题的更加丰富的方法和技巧等，最好还是要深入地看组合最优化方面的一些经典的著作，如1963年毕业于哈佛大学的Eugene Lawler教授的《组合优化》（也看到他的学生的博士学位论文都做图论），1963年至今一直在普林斯顿大学任教的Steiglitz教授和他的组合数学博士合撰的《组合优化》等都会非常有帮助。组合最优化也是NP完全和很多计算复杂性等问题和概念形成的源泉，因此，其帮助还最利于培养这方面的第六感或说直觉，这对如此艰巨的问题，诚然严格的逻辑论证和严密的检验时时都必须居于第一位、但没有深邃的直觉也就只能找到似是而非的表面‘实质’。当然，上面列出的三个证明，都应不属于爱好者之类。他们肯定知道要多参考更专业的或说本领域专家的证明。而且要看出论证是否环还贯通，对某些NP问题的证明是很难看得透彻的，有些复杂的归化证明更是似是似非。特别是一些算法的验证就是权威都很难确认。上面三个证明中，杜立智教授的2010年投稿至今已修改20次（这可以将其相比于我们都知道的标杆-哥德巴赫猜想。因陈景润院士的论文上见说3个人在1965年的3篇论文独立证明（1+3），他1966年宣布证明（1+2），其后就被卷入文革浪潮。因此，陈景润院士可能1965年才研究（1+2）。因为若他1965年以前也研究-肯定要先研究还没有解决的1+4、1+3等。可见可能陈景润院士只花一年就证明），而杜立智教授这5年来一直不断修正验证等，就同情而在这说点他的：基于我上面说的很难验证，因此这问题证明很难在权威期刊发表。而在一般期刊发表大家都知道肯定没有严审而等于不发表--也确实已发表一些证明-但专家都知道不懂这问题份量和难度的人才这样轻率。因此，我建议杜立智教授若感到相当自信了，可以将自已是如何处理的去向一些权威解释看能否说服他们来参加研讨。当然，这是非常难验证的问题，几次研讨也很难达成多少共认，但总比这样放在上面网好。总之，只有这样，才能能看出自已是否存在蒙在鼓里之处，或致命之处等。才知道是否有修改价值或应抛弃？（如邀请我去做报告研讨的南京航大宁院长1982年从美国回国就一直研究、1988年就已研究它的国防科大研究生院主管招生的副院长姜新文教授最近几年都举办研讨会。总之，一般本科出来混几年的都应懂如何做-那做为上交大本科美国研究生混了几十年的不可谓不知这些，可见这问题花了5年仍不如陈景润院士的哥德巴赫猜想那般简单明了，使得现在能收获到的也就只能先虚晃几枪来阿Q般自我补偿安慰。总之，到目前为止杜教授使用的都只能称得上是虚招--这不仅是因没有足够自信更因似乎看到自身和课题本身可能永远都…才，诶

这里附一个可参考的这里是一个“算法与图论”网

1993年完成法国贡比涅大学（Université de Technologie de Compiègne）计算机博士论文并为NP问题开启了20多年寻师访友，现是Université de Picardie Jules Verne副教授的柳渝的不确定性的困惑和NP理论博客；郝克刚

正如柳渝所说“1993年获得法国UTC计算机博士论文，就步入了法国PJV大学的教学和研究之路，并为NP理论已做了20多年寻师访友之旅。即关于“NP理论”的研究，缘起于“计算复杂性理论”教学的“奇怪”经验。“计算复杂性理论”是计算机课程的一部分，但是这部分的讲授，却令自己困惑不已。因为每次讲完后不久，就把讲授的内容几乎忘得一干二尽，只剩下…。而用于研究之一的各种启发式算法虽然层出不穷，但理论与实践严重脱节，自己不禁问为什么？…”