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

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

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

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

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

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

什么是P？

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

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

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

典型問題：

這個數是否是個質數？

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

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

什么是NP？

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

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

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

典型問題：

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

紅色：一個大小為3的clique

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

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

什么是PH？

代表：多項式層級結構復雜性類（Polynomial Hierarchy）

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

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

典型問題：

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

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

什么是PSPACE？

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

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

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

典型問題：

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

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

什么是BQP？

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

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

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

典型問題：

確定整數的質因子。

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

什么是EXPTIME？

代表：指數時間復雜性類（Exponential Time）

簡介：經典計算機可以在指數時間內解決的所有問題。

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

典型問題：

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

研究熱點：現如今，研究人員已經能證明EXPTIME問題和P問題不完全一致，但他們希望能證明EXPTIME不屬于PSPACE，因為前者關注時間，后者關注內存。

什么是BPP？

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

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

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

典型問題：

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

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