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

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

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

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

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

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

什么是P？

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

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

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

典型問題：

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

兩點之間的最短路徑是什么？

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

什么是NP？

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

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

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

典型問題：

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

紅色：一個大小為3的clique

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

研究熱點：P=NP是否成立？

什么是PH？

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

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

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

典型問題：

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

研究熱點：計算機科學(xué)家無法證明PH與P不同，這個問題其實相當(dāng)于P與NP問題，因為如果我們（意外地）證明P=NP，那么所有的PH問題都會坍縮到P，即P=PH。

什么是PSPACE？

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

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

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

典型問題：

P、NP和PH中的每個問題都是PSPACE問題。

研究熱點：PSPACE與P有何不同？

什么是BQP？

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

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

詳細說明：量子計算機可以在多項式時間內(nèi)解決的所有問題。

典型問題：

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

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

什么是EXPTIME？

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

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

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

典型問題：

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

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

什么是BPP？

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

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

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

典型問題：

多項式恒等檢驗問題。給定兩個公式，每個公式都生成一個包含許多變量的多項式，那么這兩個公式計算的是相同的多項式嗎？這是個BPP問題。

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