研究所概况

所长致辞 当前位置: 首页 >> 研究所概况 >> 所长致辞

    NP-hard问题或许是上帝对人类最富有魅力的挑战之一。很多NP-hard问题,比如,命题逻辑合取范式的可满足性、图染色、图的最大团、哈密尔顿圈等等,都非常简单,绝大多数有高中学历以上的人,都能在五分钟之内搞懂它们,但是要求得它们的解,却是一个非常困难的事情。很多具体的算例,即使用当前最好的计算机与最好的算法去求解,也需要几百世纪甚至更多的时间。人类之所以不得不面对 NP-hard 问题是因为它们出现在大量的实际应用中,  并构成了这些应用的瓶颈. 这就激发了大量对 NP-hard 问题的研究及求解它们的算法的开发。进入这一研究领域的门槛不高。任何具有一定逻辑思维能力与编程能力的人都能较快地开始这方面的工作。

     NP-hard问题的困难程度虽然令人烦恼,但是它也能为人类服务。例如,当今很多信息加密系统,都建立在NP-hard问题的困难上。只要NP不等于P,人们就可以相信他们的信息加密系统是安全的。

      对于一些从事NP-hard问题研究的人来说,NP-hard问题的最大魅力,还不是它们的实用意义,而是在NP-hard问题中,很可能隐藏着了解这个世界的很多奥秘的钥匙。只要一个NP-hard问题有了多项式算法,则所有的NP问题就都有了多项式算法。想想这一点都会觉得奇妙无穷。

     在求解NP-hard问题的艰难过程中,人们不断向自然界寻找灵感。比如,人们模拟蚂蚁寻找食物的方式而开发了蚂蚁算法,模拟生物遗传的方式而开发了遗传算法。在这些 ? 天人合一 ?的不断努力中,人类也许能更深刻地理解这个世界。进一步说,由于传统的方式方法几乎都己用尽了,求解NP-hard问题的突破,需要新的思维和新的方法论。也就是说,求解 NP-hard问题,不能仅停留在技术层面, 而必须上升到哲学的高度,这在科学史上是屡经检验的有效途径。众所周知,西方的大科学家通常也是大哲学家。比如,牛顿的那部划时代的著作,就题为 ?自然哲学的数学原理 ?,它开创了经典物理学;笛卡尔用他怀疑一切唯独不怀疑自己思想(我思故我在)的方法论,开创了解析几何;爱因斯坦的相对论,可以同时被认为是一本哲学著作,因为它代表了一种全新的世界观。时至今日,西方培养精英的学校里,对哲学课程的重视程度仍然令人印象深刻。我们相信,对NP-hard问题的研究与有效求解,将有助于人类提高自己的思想境界。这是一个长期的过程,在这个过程中,任何一个哪怕微小的进展都将给人们带来巨大的快乐。

      如果您对NP-hard 问题有兴趣,欢迎加入我们或与我们联系。

李初民

教授,博士生导师

计算科学理论与应用研究所 所长