作者：王垠
原文鏈接：http://www.yinwang.org/blog-cn/2019/07/21/pnp2
好幾年前曾經(jīng)寫(xiě)過(guò)一篇文章表達(dá)對(duì)計(jì)算機(jī)科學(xué)里著名的 “P vs NP” 問(wèn)題的看法。當(dāng)時(shí)正值我人生中第 N 次研究那些東西，由于看透了卻不在乎，所以寫(xiě)得特別簡(jiǎn)略。沒(méi)想到有人看到后，還以為我沒(méi)仔細(xì)學(xué)過(guò)復(fù)雜度理論，說(shuō)我信口開(kāi)河。我一般懶得談?wù)撨@種太理論的問(wèn)題，身邊也很少有人關(guān)心，所以后來(lái)干脆把文章撤了。不是我說(shuō)的有什么不對(duì)，而是我懶得跟人爭(zhēng)論。
沒(méi)想到最近又遇到有人抓住我刪掉的文章，乘機(jī)拿出來(lái)貶損我，盡其羞辱之能力。說(shuō)王垠你太自以為是了，你知不知道“P vs NP”要是解決了，世界將有天翻地覆的變化，多少的計(jì)算難題會(huì)被解決，機(jī)器學(xué)習(xí)都沒(méi)必要了，非對(duì)稱(chēng)加密全都被破解…… 跟上課似的頭頭是道滔滔不絕，幾乎把他本科算法課本上的內(nèi)容給我背了一遍，以為別人不知道一樣，卻沒(méi)有顯示出任何他自己的思想。
呃，我真是服了某些人背書(shū)冒術(shù)語(yǔ)的能力，難怪能做國(guó)內(nèi)某大廠的 P10（注：不是我的在職公司）。鑒于很多人對(duì)此類(lèi)問(wèn)題的一知半解，反倒嘲笑別人不懂，牛逼轟轟打壓其他人，我決定事后把這個(gè)問(wèn)題再詳細(xì)講一下，免得以后還要為它費(fèi)口舌。
對(duì)于初學(xué)者這篇文章有點(diǎn)門(mén)檻，需要學(xué)習(xí)一些東西?！?a target="_blank">P vs NP” 問(wèn)題屬于計(jì)算理論（Theory of Computation）的一部分——復(fù)雜度理論。計(jì)算理論不止包括復(fù)雜度理論（Complexity），還包括可計(jì)算性（Computability），也就是“停機(jī)問(wèn)題”一類(lèi)的內(nèi)容。
國(guó)內(nèi)大學(xué)的計(jì)算機(jī)教學(xué)一般在算法課上對(duì)復(fù)雜度理論有初級(jí)的講授，但很少人能夠真的理解。如果你沒(méi)有系統(tǒng)的學(xué)習(xí)過(guò)復(fù)雜度理論，我建議你研讀一下計(jì)算理論的專(zhuān)著（而不是普通的算法教材），比如 Michael Sipser 的『Introduction to the Theory of Computation』。
我當(dāng)年在 Indiana 做研究生計(jì)算理論課助教的時(shí)候，可算是把這書(shū)給看透了…… 被逼的。其中“可計(jì)算性理論”在我將來(lái)的 PL 研究中起了比較大的啟發(fā)作用，而復(fù)雜度理論的用處一般。我覺(jué)得 Sipser 的書(shū)寫(xiě)的不夠清晰透徹，但很多學(xué)校拿它做教材，好像也沒(méi)有其它特別好的替代品。
計(jì)算理論如此晦澀難懂，我認(rèn)為圖靈機(jī)是禍?zhǔn)?。如果你能理?lambda calculus，將會(huì)大大簡(jiǎn)化理解計(jì)算理論的過(guò)程。如果你想用更深刻更容易的方法理解計(jì)算理論，可以參考這篇文章的“Lambda 演算與計(jì)算理論”一節(jié)，里面會(huì)提到另一本參考書(shū)。從這篇文章你也可以看出來(lái)，我絲毫不崇拜圖靈。
“P vs NP” 真的重要嗎？
“P vs NP” 這個(gè)問(wèn)題有它的理論價(jià)值，它是有趣的問(wèn)題，里面的有些思路有啟發(fā)意義，值得花些時(shí)間來(lái)了解。但計(jì)算機(jī)科學(xué)界長(zhǎng)久以來(lái)都嚴(yán)重夸大它的重要性，把一個(gè)很普通的問(wèn)題捧上了天，吹得神乎其神。
再加上圖靈機(jī)模型在計(jì)算理論界的廣泛使用，使得這門(mén)學(xué)問(wèn)顯得異常艱深。很多人看到圖靈機(jī)就暈了，在課程上蒙混過(guò)關(guān)，考試完了就全忘了，根本無(wú)法理解里面的實(shí)質(zhì)內(nèi)容。正是因?yàn)楹芏嗳说牟幻饔X(jué)厲，使得“P vs NP”登上了它在 CS 界的寶座。
很多人做了一輩子計(jì)算機(jī)工作，做了很多巧妙的設(shè)計(jì)構(gòu)架，寫(xiě)了許許多多的代碼，解決了很多性能難題。提到“P vs NP”，雖然一輩子都沒(méi)用上這個(gè)理論，仍然頂禮膜拜。由此可見(jiàn)“不明覺(jué)厲”對(duì)于人們心理的威力。
很多人認(rèn)為“P vs NP”是計(jì)算機(jī)科學(xué)最重要的問(wèn)題。Clay 數(shù)學(xué)研究所甚至懸賞一百萬(wàn)美元解決這個(gè)問(wèn)題，把它叫做數(shù)學(xué)界的 7 個(gè)千年難題之一，跟黎曼猜想并列其中。
好幾次有人聲稱(chēng)解決了“P vs NP”，上了新聞，鬧得輿論沸沸揚(yáng)揚(yáng)，小編們吹得好像世界要天翻地覆了一樣，把他們追捧為天才苦行僧，后來(lái)卻又發(fā)現(xiàn)他們的結(jié)果是錯(cuò)的……
如果你真的理解了“P vs NP”的內(nèi)涵，就會(huì)發(fā)現(xiàn)這一切都是鬧劇。這個(gè)問(wèn)題即使得到解決，也不能給世界帶來(lái)很大變化。解決這個(gè)問(wèn)題對(duì)于現(xiàn)實(shí)的計(jì)算，作用是微乎其微的。不管 P 是否等價(jià)于 NP，我們遇到的計(jì)算問(wèn)題的難度不會(huì)因此有重大改變。
甚至有些數(shù)學(xué)家認(rèn)為“P vs NP” 根本沒(méi)有資格跟黎曼猜想一起并列于“千禧年問(wèn)題”。我倒是希望有人真的解決了它，這樣我們就可以切實(shí)的看到這有什么意義。
“P vs NP” 也許不是愚蠢的問(wèn)題，但計(jì)算機(jī)科學(xué)界幾十年以來(lái)夸大它的重要性的做法，是非常愚蠢的，讓整個(gè)領(lǐng)域蒙羞。
真正重要的數(shù)學(xué)問(wèn)題被解決，應(yīng)該對(duì)現(xiàn)實(shí)世界具有強(qiáng)大的作用。這種作用可以是“潛在的”，它的應(yīng)用可以發(fā)生在很久以后的將來(lái)，但這必須能夠被預(yù)見(jiàn)到。數(shù)學(xué)家們把這叫做“applicable result”（注意不叫 applied 或者 practical）。否則這個(gè)數(shù)學(xué)問(wèn)題就只能被叫做“有理論價(jià)值”，“有趣”，而不能叫做“重要”。即使所謂“純數(shù)學(xué)”，也應(yīng)該有可以預(yù)見(jiàn)的效果。
很多數(shù)學(xué)家都明白黎曼猜想（Riemann hypothesis）的重要性。大數(shù)學(xué)家希爾伯特說(shuō)過(guò)：“如果我沉睡了三千年醒過(guò)來(lái)，我的第一句話會(huì)是‘黎曼猜想被解決了嗎？’” 假設(shè)希爾伯特還在世，他會(huì)對(duì)解決“P vs NP”有同樣的渴望嗎？我覺(jué)得不會(huì)。實(shí)際上，很多數(shù)學(xué)家都覺(jué)得“P vs NP”的重要性根本沒(méi)法和黎曼猜想相提并論，因?yàn)槲覀冾A(yù)見(jiàn)不到它會(huì)產(chǎn)生任何重要的效果。
什么是多項(xiàng)式時(shí)間？
很多人提到“P vs NP”就會(huì)跟你吹噓，P 如果等于 NP，世界將有天翻地覆的變化。許許多多我們以前沒(méi)法辦到的事情，都將成為現(xiàn)實(shí)。非對(duì)稱(chēng)加密技術(shù)會(huì)被破解，生物化學(xué)將得到飛躍，機(jī)器學(xué)習(xí)將不再有必要……
這些人都忽略了一個(gè)重要的問(wèn)題：什么是多項(xiàng)式時(shí)間。盲目的把“多項(xiàng)式”等同于“容易”和“高效”，導(dǎo)致了對(duì) “P vs NP” 重要性的嚴(yán)重夸大。
n100 是不是多項(xiàng)式？是的。n1000000 也是多項(xiàng)式。n100100 也是多項(xiàng)式，n100100100 也是多項(xiàng)式…… 實(shí)際上，只要 n 的指數(shù)是常數(shù)，它就是一個(gè)多項(xiàng)式，而 n 的指數(shù)可以是任意大的常數(shù)！n 的指數(shù)可以是任意大的常數(shù)！n 的指數(shù)可以是任意大的常數(shù)！重要的事情說(shuō)三遍。
時(shí)間復(fù)雜度 n100100100 的算法，能用嗎？所以即使 P=NP，你需要的計(jì)算時(shí)間仍然可以是宇宙毀滅 N 次，其中 N 是任意的常數(shù)。
說(shuō)到這里，又會(huì)有人跟我說(shuō)你不懂，當(dāng) n 趨近于無(wú)窮的時(shí)候，非多項(xiàng)式總會(huì)在某個(gè)時(shí)候超越多項(xiàng)式，所以當(dāng) n “足夠大”的時(shí)候，多項(xiàng)式時(shí)間的算法總是會(huì)更好。很可惜，“無(wú)窮”對(duì)于現(xiàn)實(shí)的問(wèn)題是沒(méi)有意義的。任何被叫做“重要”的問(wèn)題，都應(yīng)該在合理的時(shí)間內(nèi)得到結(jié)果。
我們關(guān)心的要點(diǎn)不應(yīng)該是“足夠大”，而是“具體要多大”。精確的量化，找到實(shí)際可以用的區(qū)間，這才是合格的科學(xué)家該有的思路。計(jì)算機(jī)科學(xué)里，大 O 表示法泛濫成災(zāi)，只看最高次冪，忽略系數(shù)和常數(shù)項(xiàng)，也是常見(jiàn)的誤區(qū)。我也曾經(jīng)沉迷于如何把 O(n3) 的算法降低到 O(n2.9)，現(xiàn)在回頭才發(fā)現(xiàn)當(dāng)年是多么的幼稚。
“多項(xiàng)式時(shí)間”這個(gè)概念太寬泛太籠統(tǒng)。以如此籠統(tǒng)的概念為基礎(chǔ)的理論，不可能對(duì)現(xiàn)實(shí)的計(jì)算問(wèn)題產(chǎn)生意義。我們關(guān)心的不應(yīng)該僅僅是“是否多項(xiàng)式”，而是“具體是什么樣的多項(xiàng)式”。6n20 + 26n7 + 200，1000n3 + 8n2 + 9，…… 每一個(gè)多項(xiàng)式的曲線都是很不一樣的，在各個(gè)區(qū)間它們的差別也是不一樣的。多項(xiàng)式的冪，系數(shù)，常數(shù)項(xiàng)，它們的不同都會(huì)產(chǎn)生重大的差異。
這就是為什么“P=NP”沒(méi)有很大意義，因?yàn)?P 本身太籠統(tǒng)，其內(nèi)部的差異可以是天壤之別。與其試圖籠統(tǒng)的證明 P 等價(jià)于 NP，還不如為具體的問(wèn)題想出實(shí)質(zhì)意義上高效的算法，精確到冪，系數(shù)，常數(shù)項(xiàng)。
更進(jìn)一步看，這些“復(fù)雜度”的數(shù)學(xué)公式，不管是多項(xiàng)式還是指數(shù)，不管你的冪，系數(shù)常數(shù)項(xiàng)有多精確，終究難以描述現(xiàn)實(shí)系統(tǒng)的特性。物理的機(jī)器有各種分級(jí)的 cache，并行能力，同步開(kāi)銷(xiāo)，傳輸開(kāi)銷(xiāo)，各種瓶頸…… 最后你發(fā)現(xiàn)性能根本無(wú)法用數(shù)學(xué)公式來(lái)表達(dá)，它根本不是一個(gè)數(shù)學(xué)問(wèn)題，而是一個(gè)物理問(wèn)題，工程問(wèn)題。這就像汽車(chē)引擎的功率一樣，只有放到測(cè)試設(shè)備（Dyno）上面，通過(guò)系統(tǒng)的測(cè)量過(guò)程才能得到。
有些理論家喜歡小看“工程”，自以為會(huì)分析復(fù)雜度就高高在上的樣子，而其實(shí)呢，工程和物理才是真實(shí)的。數(shù)學(xué)只是粗略描述物理和工程的工具。
P!=NP 有意義嗎？
“P vs NP”問(wèn)題有兩種可能性：P=NP（等價(jià)），或者 P!=NP（不等價(jià)）。以上我說(shuō)明了 P=NP 的意義不大，那么要是 P!=NP 呢？
很多人會(huì)跟你說(shuō)，要是一個(gè)問(wèn)題是 NP-Hard，然后又有 P!=NP，那么我們就知道這個(gè)問(wèn)題沒(méi)有多項(xiàng)式時(shí)間的算法存在，就避免了為多項(xiàng)式時(shí)間算法浪費(fèi)時(shí)間了。這不也有一些價(jià)值嗎？
我并沒(méi)有否認(rèn) P!=NP 是有那么一點(diǎn)價(jià)值：在某些時(shí)候它也許避免了浪費(fèi)時(shí)間。但這種價(jià)值比較小，而且它具有誤導(dǎo)性。
一個(gè)常見(jiàn)的 NP-Hard 問(wèn)題是 SAT。如果 P!=NP，那么大家就應(yīng)該放棄為它找到高效的算法嗎？如果大家都這樣想，那么現(xiàn)在的各種高效的 SAT solver 就不存在了。實(shí)際上，利用隨機(jī)算法，我們?cè)诖蠖鄶?shù)時(shí)候都能比較快的解決 SAT 問(wèn)題。
問(wèn)題在于，“P vs NP”關(guān)心的只是“最壞情況”，而最壞情況也許非常罕見(jiàn)。有些問(wèn)題大部分實(shí)際的情況都可以高效的解決，只有少數(shù)變態(tài)的情況會(huì)出現(xiàn)非常高的復(fù)雜度。為了這少數(shù)情況放棄大多數(shù)，這就是“P vs NP”的誤導(dǎo)。
如果因?yàn)?P!=NP，你認(rèn)為 NP-Hard 的問(wèn)題就沒(méi)有高效的算法，那你也許會(huì)誤以為你可以利用這些“難題”來(lái)做非對(duì)稱(chēng)加密。然而 NP-Hard 并不等于沒(méi)法快速解決，所以要是你因此被誤導(dǎo)，也許會(huì)設(shè)計(jì)出有漏洞的加密算法。
即使 P!=NP，我們?nèi)匀徊荒芊艞墝ふ抑匾?NP-Hard 問(wèn)題的高效算法，所以確切的證明 P!=NP 的價(jià)值也不是那么重要了。其實(shí)你只要知道 P=NP “大概不可能”，就已經(jīng)能起到“節(jié)省時(shí)間”的目的了。你沒(méi)必要證明它。
什么是 NP？
這一節(jié)我來(lái)講講“P vs NP”里的“NP”到底是什么。內(nèi)容比較深，看不懂的人可以跳過(guò)。
很多人都沒(méi)搞明白 NP 是什么就開(kāi)始夸夸其談“P vs NP”的價(jià)值。 經(jīng)常出現(xiàn)的錯(cuò)誤，是把 NP 等同于“指數(shù)時(shí)間”。實(shí)際上 NP 代表的是“Nondeterministic Polynomial time”，也就是“非確定性圖靈機(jī)”（nondeterministic Turing machine）能在多項(xiàng)式時(shí)間解決的那些問(wèn)題。
什么是“非確定性圖靈機(jī)”？如果你把課本上那堆圖靈機(jī)的定義看明白看透了，然后又理解了程序語(yǔ)言理論，你會(huì)發(fā)現(xiàn)所謂“非確定性圖靈機(jī)”可以被很簡(jiǎn)單的解釋。
你可以把我們通常用到的程序看作是“確定性圖靈機(jī)”（deterministic Turing machine）。它們遇到條件分支，在同一個(gè)時(shí)刻只能走其中一條路，不能兩邊同時(shí)探索。
那么“非確定性圖靈機(jī)”呢？你可以把“非確定性圖靈機(jī)”想象成一個(gè)具有“超能力”的計(jì)算機(jī)，它遇到分支語(yǔ)句的時(shí)候，可以同時(shí)執(zhí)行 True 和 False 兩個(gè)分支。它能夠同時(shí)遍歷任意多的程序分支，這是一臺(tái)具有超能力的機(jī)器！
所以“P vs NP”的含義大概就是這樣：請(qǐng)問(wèn)那些需要非確定性圖靈機(jī)（超能力計(jì)算機(jī)）在多項(xiàng)式時(shí)間才能解決的問(wèn)題，能夠用確定性圖靈機(jī)（普通計(jì)算機(jī)）在多項(xiàng)式時(shí)間解決嗎？
現(xiàn)在問(wèn)題來(lái)了，具有如此超能力的機(jī)器存在嗎？答案當(dāng)然是“No！” 就算是量子計(jì)算機(jī)做成功了，也不可能具有這樣的計(jì)算能力。沒(méi)有人知道如何造出非確定性圖靈機(jī)，人們沒(méi)有任何頭緒它如何能夠存在。
所以 “P vs NP” 這個(gè) 問(wèn)題的定義，是基于一個(gè)完全假想的機(jī)器——非確定性圖靈機(jī)。既然是假象的機(jī)器，為什么一定要是“非確定圖靈機(jī)”呢？為什么不可以是其它具有超能力的東西？
仔細(xì)想想吧，“非確定性圖靈機(jī)”對(duì)于現(xiàn)實(shí)的意義，就跟 Hogwarts 魔法學(xué)校和哈利波特對(duì)于現(xiàn)實(shí)的意義一樣。我們?yōu)槭裁床谎芯俊癙 vs HP”呢，其中 H 代表 Harry Potter。HP 定義為：哈利波特能夠在多項(xiàng)式時(shí)間解決的問(wèn)題。
“P vs NP”問(wèn)題：請(qǐng)問(wèn)那些需要非確定性圖靈機(jī)（超能力計(jì)算機(jī)）在多項(xiàng)式時(shí)間才能解決的問(wèn)題，能夠用確定性圖靈機(jī)（普通計(jì)算機(jī)）在多項(xiàng)式時(shí)間解決嗎？
“P vs HP”問(wèn)題：請(qǐng)問(wèn)那些需要哈利波特在多項(xiàng)式時(shí)間才能解決的問(wèn)題，能夠用確定性圖靈機(jī)（普通計(jì)算機(jī)）在多項(xiàng)式時(shí)間解決嗎？
我不是開(kāi)玩笑，仔細(xì)回味一下 “P vs NP” 和 “P vs HP” 的相似性吧。也許你會(huì)跟我一樣意識(shí)到 NP 這個(gè)概念本身就是虛無(wú)的。我不明白“一個(gè)不存在的機(jī)器能在多項(xiàng)式時(shí)間解決的問(wèn)題”，這樣的說(shuō)法有何意義，基于它的理論又有什么科學(xué)價(jià)值。
非確定性圖靈機(jī)存在的意義，也許只是因?yàn)樗梢员蛔C明等價(jià)于其它一些常見(jiàn)的問(wèn)題，比如 SAT。計(jì)算理論書(shū)籍一般在證明 SAT 與 非確定性圖靈機(jī)等價(jià)性之后，就完全拋掉了非確定性圖靈機(jī)，之后的等價(jià)性證明都是通過(guò) SAT 來(lái)進(jìn)行。
我覺(jué)得 NP 這個(gè)概念其實(shí)是在故弄玄虛。我們完全可以從 SAT 本身出發(fā)去發(fā)展這個(gè)理論，而不需要設(shè)想一個(gè)具有超能力的機(jī)器。我們可以有一個(gè)問(wèn)題叫做“P vs SAT”，而不出現(xiàn) NP 這個(gè)概念。
（有點(diǎn)扯遠(yuǎn)了）
其它質(zhì)疑 P vs NP 價(jià)值的人
有人認(rèn)為我質(zhì)疑 P vs NP 的價(jià)值是一知半解信口開(kāi)河，然而我并不是第一個(gè)質(zhì)疑它的人。很多人對(duì) P vs NP 都有類(lèi)似的疑惑，但因?yàn)檫@個(gè)問(wèn)題的地位如此之高，沒(méi)人敢站出來(lái)。只要你開(kāi)口，一群人就會(huì)居高臨下指責(zé)你基礎(chǔ)課程沒(méi)學(xué)好，說(shuō)你眼界太窄…… 再加上那一堆紛繁復(fù)雜基于圖靈機(jī)的證明，讓你有苦說(shuō)不出。
由于這個(gè)原因，我從來(lái)沒(méi)敢公開(kāi)表達(dá)我的觀點(diǎn)，直到我發(fā)現(xiàn) Doron Zeilberger 的這篇文章。Zeilberger 是個(gè)數(shù)學(xué)家，Rutgers 大學(xué)的數(shù)學(xué)系教授。在那之前他開(kāi)了個(gè)玩笑，戲稱(chēng)自己證明了 P=NP，還寫(xiě)了篇像模像樣的論文。在文章里他告誡大家：不要愛(ài)上你的模型（Don’t Fall In Love With Your Model）。他這句話說(shuō)到了我心里。
你還能在網(wǎng)絡(luò)上找到其它人對(duì)“P vs NP”的質(zhì)疑，比如這篇來(lái)自于一位專(zhuān)門(mén)研究計(jì)算理論的學(xué)者：
? Is P=NP an Ill Posed Problem?
我覺(jué)得他講的也很在理。正是在這些人的鼓舞之下，我隨手寫(xiě)出了之前對(duì)“P vs NP” 的質(zhì)疑。只言片語(yǔ)里面，融入了我多年的深入學(xué)習(xí)，研究和思考。
總結(jié)
看這篇文章很累吧？我寫(xiě)著也累。對(duì)于我來(lái)說(shuō)這一切都已經(jīng)那么明了，真的不想費(fèi)口舌。但是既然之前已經(jīng)說(shuō)出來(lái)了，為了避免誤解，我仍然決定把這些東西寫(xiě)下來(lái)擺在這里。如果你暫時(shí)看不懂可以先放在一邊，等到了需要深入研究計(jì)算理論，想得頭痛的時(shí)候再來(lái)看。你也許會(huì)感謝我。
我希望嚴(yán)謹(jǐn)?shù)挠?jì)算機(jī)科學(xué)工作者能夠理解我在說(shuō)什么，反思一下對(duì)“P vs NP”的理解。計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生應(yīng)該理解“P vs NP”理論，但不必沉迷其中。這并不是一個(gè)值得付出畢生精力去解決的問(wèn)題。計(jì)算機(jī)科學(xué)里面還有其它許多有趣而重要的問(wèn)題需要你們?nèi)ヌ剿?。如果你覺(jué)得計(jì)算機(jī)科學(xué)都不過(guò)癮，你可以去證明黎曼猜想啊 :)
當(dāng)然所有這些都是我的個(gè)人觀點(diǎn)，我沒(méi)有強(qiáng)求任何人接受它們。強(qiáng)迫別人接受自己的觀點(diǎn)是不可以的，但想阻止別人表達(dá)對(duì)此類(lèi)問(wèn)題的質(zhì)疑，也是不可以的，因?yàn)槲覀兩钤谧杂傻氖澜纭?/p>
沒(méi)人想搶走你們的玩具，但不要忘了，它只是玩具。
