路西

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

什么是P和NP？

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

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

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

最難的NP問(wèn)題與NP的外界

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

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

P=NP？

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

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

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

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