路西

2000年初，美國克雷數(shù)學(xué)研究所選定了7個(gè)“千禧年大獎(jiǎng)難題”：NP完全問題、霍奇猜想、龐加萊猜想、黎曼猜想、楊-米爾斯存在性和質(zhì)量缺口、納衛(wèi)爾-斯托克方程和BSD猜想。NP完全問題位于這個(gè)數(shù)學(xué)難題清單的第一項(xiàng)，是計(jì)算機(jī)科學(xué)領(lǐng)域最大的難題，也可能是所有數(shù)學(xué)問題中最難的一項(xiàng)。P完全問題即P=NP？問題由史蒂芬·庫克在1971首次提出，它是七大千禧年大獎(jiǎng)問題中最年輕的問題，同時(shí)也是最好理解的一個(gè)。

什么是P和NP？

在我們的生活中，有些數(shù)學(xué)問題可以很快地解決，比如買東西結(jié)賬;但是有些數(shù)學(xué)問題卻要花大量的時(shí)間去解決，比如下象棋。隨著數(shù)學(xué)和計(jì)算機(jī)科學(xué)的發(fā)展，針對(duì)于部分比較難解決的數(shù)學(xué)問題，人們想出了更好的算法，所以解決它們需要的時(shí)間就變少了。將問題分為快速解決和慢速解決兩種的話，加減乘除是可以快速解決的問題，而下象棋是慢速解決的問題，當(dāng)然還有許多的問題，我們不清楚應(yīng)該將它們分于哪一類。于是我們就用了包含P與NP的更精準(zhǔn)的定義去分類這些數(shù)學(xué)問題。

P問題包含所有可以被計(jì)算機(jī)程序快速解決的問題，比如加減乘除。NP問題是指如果給出一組問題的答案，你至少可以在合理的時(shí)間里檢查這個(gè)答案是否正確。例如給定一個(gè)數(shù)41607317，如果對(duì)這個(gè)較大數(shù)做質(zhì)因數(shù)分解，是有些難度的。但是如果給出一個(gè)可能的答案比如8699和4783，你可以通過將兩個(gè)數(shù)相乘對(duì)比原來的大數(shù)，很快地得出8699和4783這兩個(gè)數(shù)是正確答案。世界上有很多的問題，我們很難去找到它的答案，但是如果給出了答案，驗(yàn)證這個(gè)答案是否正確卻是相對(duì)簡單的。例如，做出數(shù)獨(dú)的答案，可以很簡單的驗(yàn)證結(jié)果的正誤，但是我們至今沒有找到一個(gè)可以完美解決所有數(shù)獨(dú)問題的最優(yōu)途徑（想象1000×1000級(jí)的數(shù)獨(dú)，而不是9×9的），做數(shù)獨(dú)往往還是用試數(shù)的方法（即枚舉法）。

毫無疑問，NP問題包含P問題，因?yàn)閷?duì)于P問題只需按部就班地算出問題的答案進(jìn)行對(duì)比就可以了。

最難的NP問題與NP的外界

所有人都認(rèn)為NP所包含的問題比P所包含的問題要多，即使有些問題還沒有被發(fā)現(xiàn)，當(dāng)然現(xiàn)在還沒有人能夠證明這一點(diǎn)。數(shù)學(xué)家發(fā)現(xiàn)很多NP問題其實(shí)是互通的，比如數(shù)獨(dú)問題的本質(zhì)和蛋白質(zhì)折疊問題是一樣的，如果你能找到解決數(shù)獨(dú)問題的最優(yōu)算法，蛋白質(zhì)折疊這一21世紀(jì)最重要的生物學(xué)問題也將迎刃而解。數(shù)獨(dú)和蛋白質(zhì)折疊問題屬于NP中的一個(gè)下屬分類NPC（NP-Complete）問題。NPC問題是NP中最難的一部分，這些問題的復(fù)雜性（解決問題需要的時(shí)間和空間）與整個(gè)類的復(fù)雜性相關(guān)聯(lián)，如果我們能快速解決某一NPC問題，那么所有的NP問題都能快速解開。

NP問題需要花很長的時(shí)間去求解，但是很容易驗(yàn)證結(jié)果的正確性。在NP之外，還存在著一些問題，驗(yàn)證這些問題的結(jié)果甚至都是不可能的，例如，我們很難判斷象棋中的某一步是不是最好的。還有Co-NP問題，與NP問題不同的是，Co-NP問題可以在合理的時(shí)間內(nèi)很容易地排出錯(cuò)誤解，而不是驗(yàn)證正確解。Co-NP問題與NP問題是否是互通的，我們也不得而知。除此之外，還有非常多的問題分類，每一個(gè)分類都需要花費(fèi)大量的時(shí)間去解釋。

P=NP？

NP是舉足輕重的，因?yàn)樗艘恍┓浅Ｖ匾膯栴}，比如：旅行商問題（給定一系列城市和每對(duì)城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路），電路設(shè)計(jì)問題和數(shù)據(jù)庫問題等，如果這些問題得到解決，我們的生活將會(huì)有翻天覆地的變化。因此，數(shù)學(xué)家們一直積極地解決各種數(shù)學(xué)問題。在這個(gè)努力的過程中，我們有時(shí)會(huì)幸運(yùn)地發(fā)現(xiàn)一些NP問題實(shí)際上是P問題，我們就找到了解決這個(gè)問題的捷徑，同時(shí)仍有很多的NP問題還不能被歸類為P?？茖W(xué)家開始思考：NP中的所有問題最終都會(huì)變成P問題嗎？還是有些NP問題就是比P問題難解決的多？這就是著名的P=NP？問題。

解決P=NP猜想的方法有兩種，一種是找到NP問題的解決算法，那么所有的NP問題就都可以解決了;另一種就是從數(shù)學(xué)理論上證明這樣的算法不存在。但是現(xiàn)在的很多數(shù)學(xué)家在證明這一問題上存在誤區(qū)，他們往往假設(shè)一種可能的解決算法，然后設(shè)法證明這種算法的錯(cuò)誤性或不存在。實(shí)際上證明P=NP問題本身就是NP問題之一，這讓我們感到更加的困惑。

如果P=NP，那么我們就能找到簡單的解決問題的方法，換言之，就是人類在解決復(fù)雜問題的時(shí)候是有捷徑的。計(jì)算機(jī)一下子就可以變得非常的“聰明”，可以在十分混亂的局面中，快速找到一個(gè)捷徑。當(dāng)獲知了所有的信息以后，計(jì)算機(jī)可以在極短的時(shí)間里，對(duì)證券市場(chǎng)、天氣、球賽結(jié)果做出非常準(zhǔn)確的預(yù)測(cè);計(jì)算機(jī)能夠輕松找到一個(gè)算法，來知道藝術(shù)作品是如何直擊人心的，于是計(jì)算機(jī)可以為每個(gè)人定制出他最喜愛的音樂、藝術(shù)作品。與此同時(shí)，人工智能可以快速的自我優(yōu)化，意味著人類的末日可能到來了;密碼學(xué)的基礎(chǔ)也很容易就會(huì)被破解，我們每個(gè)人都毫無秘密可言。

P=NP嗎？數(shù)學(xué)家還沒有答案。