路西

2000年初，美国克雷数学研究所选定了7个“千禧年大奖难题”：NP完全问题、霍奇猜想、庞加莱猜想、黎曼猜想、杨-米尔斯存在性和质量缺口、纳卫尔-斯托克方程和BSD猜想。NP完全问题位于这个数学难题清单的第一项，是计算机科学领域最大的难题，也可能是所有数学问题中最难的一项。P完全问题即P=NP？问题由史蒂芬·库克在1971首次提出，它是七大千禧年大奖问题中最年轻的问题，同时也是最好理解的一个。

什么是P和NP？

在我们的生活中，有些数学问题可以很快地解决，比如买东西结账;但是有些数学问题却要花大量的时间去解决，比如下象棋。随着数学和计算机科学的发展，针对于部分比较难解决的数学问题，人们想出了更好的算法，所以解决它们需要的时间就变少了。将问题分为快速解决和慢速解决两种的话，加减乘除是可以快速解决的问题，而下象棋是慢速解决的问题，当然还有许多的问题，我们不清楚应该将它们分于哪一类。于是我们就用了包含P与NP的更精准的定义去分类这些数学问题。

P问题包含所有可以被计算机程序快速解决的问题，比如加减乘除。NP问题是指如果给出一组问题的答案，你至少可以在合理的时间里检查这个答案是否正确。例如给定一个数41607317，如果对这个较大数做质因数分解，是有些难度的。但是如果给出一个可能的答案比如8699和4783，你可以通过将两个数相乘对比原来的大数，很快地得出8699和4783这两个数是正确答案。……