你真的理解什么是P，什么是NP嗎？

編者按：說起復(fù)雜度，相信不少人會想到Jeff Dean面試Google時(shí)的一個(gè)笑話，面試官問：如果P=NP成立，你能推導(dǎo)出哪些結(jié)論？年輕的Dean面不改色：P=0或N=1。雖然這個(gè)經(jīng)典段子令人回味無窮，但你真的理解什么是P，什么是NP嗎？

對于計(jì)算機(jī)來說，做什么事是容易的，做什么事是幾乎不可能完成的，這些問題構(gòu)成了計(jì)算復(fù)雜度的核心。

如果計(jì)算機(jī)科學(xué)家希望能用一個(gè)叫做“復(fù)雜度”的東西對問題進(jìn)行分類，那么一個(gè)問題有多困難？這會是他們需要面對的基本任務(wù)。所謂“復(fù)雜度”，它可以被看作是包含所有計(jì)算問題的一系列組，組間劃分依據(jù)是解決具體問題所耗費(fèi)的資源是否在某個(gè)固定數(shù)量以下，這里的資源可以是時(shí)間，也可以是內(nèi)存。

以一個(gè)玩具問題為例：123,456,789,001是不是質(zhì)數(shù)？對于這個(gè)問題，計(jì)算機(jī)科學(xué)家可以用現(xiàn)有算法快速得到答案——123,456,789,001不是質(zhì)數(shù)。無論這個(gè)數(shù)字是否會變得越來越大，算法計(jì)算所需資源會一直在可控范圍內(nèi)，不會突破天際。

那么，新的問題產(chǎn)生了：它的質(zhì)因子有哪些，除了1和本身，它還能被哪些數(shù)整除？通常情況下，我們認(rèn)為它和上個(gè)問題擁有不同的“復(fù)雜度”。驗(yàn)證一個(gè)數(shù)是不是質(zhì)數(shù)很簡單，但找出它的所有質(zhì)因子就很困難。目前，算法還不能在短時(shí)間內(nèi)解決這個(gè)問題，除非我們已經(jīng)有了成熟的量子計(jì)算機(jī)。

“復(fù)雜度”本身存在大量不同的類別，但在大多數(shù)情況下，我們還無法證明這一類“復(fù)雜度”和那一類“復(fù)雜度”有哪些顯著不同。這些差異可能是微妙的，也可能是明顯的。因此對于大多數(shù)人來說，明確分類各種復(fù)雜度也是一個(gè)艱巨的挑戰(zhàn)。

什么是P？

代表：多項(xiàng)式時(shí)間復(fù)雜性類（Polynomial time）

簡介：所有P問題都能被經(jīng)典計(jì)算機(jī)（非量子計(jì)算機(jī)）輕松解決。

詳細(xì)說明：如果一個(gè)問題是P問題，那么它必須滿足在多項(xiàng)式時(shí)間nc內(nèi)驗(yàn)證一個(gè)算法問題的實(shí)例是否有解 ，其中n是輸入長度，c是個(gè)常數(shù)。

典型問題：

這個(gè)數(shù)是否是個(gè)質(zhì)數(shù)？

兩點(diǎn)之間的最短路徑是什么？

研究熱點(diǎn)：P=NP是否成立？如果成立，它將顛覆計(jì)算機(jī)科學(xué)，并使大多密碼學(xué)內(nèi)容在一夜之間失效（當(dāng)然大多數(shù)人還是認(rèn)為P!=NP）。

什么是NP？

代表：非定常多項(xiàng)式時(shí)間復(fù)雜性類（Nondeterministic Polynomial time）

簡介：如果給出了一個(gè)解，所有NP問題都能被經(jīng)典計(jì)算機(jī)快速驗(yàn)證。

詳細(xì)說明：如果一個(gè)問題有一個(gè)解，且能在多項(xiàng)式時(shí)間內(nèi)證明這是個(gè)正解，那么這就是個(gè)NP問題。例如，假設(shè)問題的輸入是字符串X，我們的目標(biāo)是驗(yàn)證問題的解為“是”，那么我們就需要一個(gè)證明——字符串Y，用它在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證答案確實(shí)是“是”。

典型問題：

分團(tuán)問題。想象一個(gè)帶邊和點(diǎn)的圖形，我們把它當(dāng)成Facebook的社交網(wǎng)絡(luò)，一個(gè)節(jié)點(diǎn)代表一個(gè)用戶，如果兩個(gè)用戶是朋友關(guān)系，那么兩個(gè)節(jié)點(diǎn)通過邊連接。一個(gè)clique表示整個(gè)社交網(wǎng)絡(luò)中的一個(gè)子集，其中所有人都是彼此的朋友。那么也許有人會問：這個(gè)社交網(wǎng)絡(luò)中是否存在20人的clique？50人？100人？找到這樣一個(gè)clique就是個(gè)“NP-完全問題”（NPC），這意味著它具有NP中任何問題的最高復(fù)雜度。但是，如果問題是50個(gè)節(jié)點(diǎn)可不可以形成一個(gè)小子集，它給出了潛在答案，那么這個(gè)NP問題就很容易被驗(yàn)證。

紅色：一個(gè)大小為3的clique

旅行商問題。有許多城市，每個(gè)城市之間都有對應(yīng)的路程距離，旅行商能不能在不到具體里程數(shù)的情況下經(jīng)過所有城市。

研究熱點(diǎn)：P=NP是否成立？

什么是PH？

代表：多項(xiàng)式層級結(jié)構(gòu)復(fù)雜性類（Polynomial Hierarchy）

簡介：PH是NP的概括——它包含由NP問題發(fā)展而來的所有問題，并添加了額外的復(fù)雜度。

詳細(xì)說明：PH問題包含一些交替“量詞”的問題，使問題更加復(fù)雜。至于什么是交替“量詞”，這里有一個(gè)示例：給定X，確定是否存在Y，使得對于每個(gè)Z，都存在一個(gè)W能使R成立？問題中包含的“量詞”越多，它就越復(fù)雜，在多項(xiàng)式層級結(jié)構(gòu)中也越高。

典型問題：

確定是否存在大小為50的clique，同時(shí)沒有大小為51的clique。

研究熱點(diǎn)：計(jì)算機(jī)科學(xué)家無法證明PH與P不同，這個(gè)問題其實(shí)相當(dāng)于P與NP問題，因?yàn)槿绻覀儯ㄒ馔獾兀┳C明P=NP，那么所有的PH問題都會坍縮到P，即P=PH。

什么是PSPACE？

代表：多項(xiàng)式空間復(fù)雜性類（Polynomial Space）

簡介：PSPACE包含在限定內(nèi)存下能解決的所有問題。

詳細(xì)說明：在PSPACE問題中，你不需要關(guān)心用時(shí)，只要關(guān)注運(yùn)行算法所需的內(nèi)存。計(jì)算機(jī)科學(xué)家已證明PSPACE問題包含PH，也就是包含NP，包含P。

典型問題：

P、NP和PH中的每個(gè)問題都是PSPACE問題。

研究熱點(diǎn)：PSPACE與P有何不同？

什么是BQP？

代表：有限錯(cuò)誤量子多項(xiàng)式時(shí)間復(fù)雜性類（Bounded-error Quantum Polynomial time）

簡介：所有BQP問題都能被量子計(jì)算機(jī)輕松解決。

詳細(xì)說明：量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)解決的所有問題。

典型問題：

確定整數(shù)的質(zhì)因子。

研究熱點(diǎn)：研究人員已經(jīng)證實(shí)P?BQP?PSPACE，但他們還不能確定BQP和NP的關(guān)系，目前他們的看法是兩者互斥。

什么是EXPTIME？

代表：指數(shù)時(shí)間復(fù)雜性類（Exponential Time）

簡介：經(jīng)典計(jì)算機(jī)可以在指數(shù)時(shí)間內(nèi)解決的所有問題。

詳細(xì)說明：EXPTIME問題包含之前所有的復(fù)雜性類——P、NP、PH、PSPACE、BQP和QMA等。目前研究人員已經(jīng)證明EXPTIME和P不同——他們在其中發(fā)現(xiàn)了不屬于P的問題。

典型問題：

國際象棋、跳棋等棋類游戲都屬于EXPTIME問題。例如，如果棋盤可以是任意大小，那么在給定棋局形勢下，確定哪位棋手是優(yōu)勢方就是個(gè)EXPTIME問題。

研究熱點(diǎn)：現(xiàn)如今，研究人員已經(jīng)能證明EXPTIME問題和P問題不完全一致，但他們希望能證明EXPTIME不屬于PSPACE，因?yàn)榍罢哧P(guān)注時(shí)間，后者關(guān)注內(nèi)存。

什么是BPP？

代表：有限錯(cuò)誤概率多項(xiàng)式時(shí)間復(fù)雜性類（Bounded-error Probabilistic Polynomial time）

簡介：可以通過包含隨機(jī)元素的算法快速解決的問題。

詳細(xì)說明：BPP問題的其他條件和P問題一致，不同的是，它允許算法中包含隨機(jī)元素，包括決策隨機(jī)化，它的解是個(gè)歸一化的小數(shù)，只要接近1即可。

典型問題：

多項(xiàng)式恒等檢驗(yàn)問題。給定兩個(gè)公式，每個(gè)公式都生成一個(gè)包含許多變量的多項(xiàng)式，那么這兩個(gè)公式計(jì)算的是相同的多項(xiàng)式嗎？這是個(gè)BPP問題。

研究熱點(diǎn)：計(jì)算機(jī)科學(xué)家想知道BPP是否是P。如果是，那這就意味著每個(gè)隨機(jī)算法都可以去隨機(jī)化。