複雜問題的簡單指南
原標題：複雜問題的簡單指南
原創： Kevin
編譯：仔仔
授權轉自：原理
計算機能夠做什麼？又有哪些問題計算機幾乎不可能解決？這些問題構成了計算複雜度的核心。這裡，我們呈現了一張關於計算複雜度的地圖：
○各種「複雜性類」（complexity class）將問題排序為層級結構：一個類可能包含另一個類的所有問題，以及其他需要額外計算資源的問題。
一個問題從本質上來說能有多難？這是計算機科學家的基本任務，他們希望將問題歸類到所謂的複雜性類（complexity class）中。複雜性類包含所需計算資源少於一定數量的所有計算問題，這種計算資源通常指時間或內存。
以一個非常大的數字123456789001為例，一個問題可能會是：這個數字是質數、也就是只能被1和它自己整除嗎？計算機科學家可以用快速演算法（fast algorithm）解決這個問題，這種演算法不會因為數字變得任意大而陷入停頓。對於123456789001這個例子，答案是它並不是質數。
然後我們可能會問：這個數字的質因數是什麼？對於這個問題，並不存在第一個問題中的快速演算法——除非使用量子計算機。因此，計算機科學家認為這兩個問題屬於不同的複雜性類。
存在許多不同的複雜性類，儘管大多數情況下，研究者還不能證明一個類完全區別於其他類。證明這些分類間的區別是該領域最困難和最重要的開放性問題之一，這就是為什麼五月底Ran Raz和Avishay Tal這兩位計算機科學家的證明結果被認為是如此重要。他們解決了科學家們自1993年就開始尋求答案的問題，證明了存在一些只有量子計算機能夠解決、而無論現在或未來的經典計算機都永遠不可能解決的問題，也就表明了量子計算機和經典計算機的兩個複雜性類確實不同。（進一步閱讀《誤解帶來的樂觀與恐慌》）
複雜性類之間的差異可以是微妙的，也可以是明顯的，如何正確分類是一個挑戰。因此，我們將介紹以下10個基本的複雜性類作為一個入門，希望你看完後再也不會混淆BPP和BQP了。
P
代表：多項式時間（Polynomial time）
簡單介紹：經典（非量子）計算機能夠輕易解決的所有問題。
詳細介紹：P類的演算法必須在多項式時間 t=n^c 內停止並輸出正確的結果，其中n是輸入的長度，c是常數。
典型問題：
- 一個數是質數嗎？
- 兩點之間的最短路徑是什麼？
NP
代表：非確定性多項式時間（Nondeterministic Polynomial time）
簡單介紹：只要給出一個解，經典計算機就能夠快速驗證給出的解是否正確的所有問題。
詳細介紹：如果給定「是」的答案，可在多項式時間內確定這個答案是正確的，這就是一個NP問題。如果輸入是一個字元串X，需要判斷答案是否為「是」，那麼這個簡短的證明將是另一個字元串Y，然後，在多項式時間內，Y被用來驗證答案是否為「是」。（Y有時被稱為「短時見證」（short witness），NP類的所有問題都有「短時見證」，這些「短時見證」使得問題能夠迅速被解決。）
典型問題：
- 分團問題（Clique problem）
想像一個有邊和節點的圖形，例如Facebook的社交網路圖，其中節點是個人，如果兩個人建立好友關係，兩個節點就被一條邊連接。小團體（Clique）是整個圖形的一個子集，其中每一個人都是其他人的朋友，也就是其中任意兩個節點彼此連接。有人或許會問：存在20個人的小團體嗎？50個人呢？100個人呢？尋找這樣的小團體是圖論領域的一個「NP完全」（NP-complete）問題，NP完全意味著這是NP類問題中最複雜的一種。然而，如果給出了一個潛在的答案，比如說50個節點可以或不可以形成一個小團體，那麼問題就迎刃而解了。
○6個節點的網路圖中大小為3的小團體。來源 | Wikepedia
- 最短路徑問題（Travelling salesman problem）
考慮一系列城市，其中每一對城市之間的距離是已知的，有沒有一種方法能夠以最短的距離穿越所有的城市呢？例如，一個旅行推銷員能夠穿越美國各個州的首府，而將行程控制在11000英里內嗎？（進一步閱讀：《一位旅行家》）
○最短路徑問題。來源 | Wikepedia
NP-Complete
代表：NP 完全
簡單介紹：在多項式時間內，所有NP類問題都能夠被規約到的問題的集合。
詳細介紹：在多項式時間內，如果所有NP類問題都能被轉化為另一個NP問題，那麼這個轉化後的NP類問題就稱為NP完全問題。NP完全問題滿足兩個條件：1. 本身是NP類問題。2. 所有NP類問題都能規約到該問題。
典型問題：
- 給一個整數集合，證明是否存在一個非空子集，使得該集合內的數字和為0。
NP-Hard
代表：NP困難
簡單介紹：在多項式時間內，能夠被規約到該問題的所有問題。
詳細介紹：在多項式時間內，如果所有問題都能被轉化為另一個問題，那麼這個轉化後的問題就稱為NP困難問題。它滿足NP完全問題的第二個條件，但不一定要滿足第一條，即NP困難問題未必能在多項式時間內驗證。
典型問題：
- 停機問題（詳見：《一個無法被證明的邏輯問題》）
○左側是在假定P≠NP的前提下，P，NP，NP-Complete與NP-Hard四個複雜性類的關係，右側則是假定P=NP的前提下它們的關係。 | 來源 Wikipedia
PH
代表：多項式層級結構（Polynomial Hierarchy）
簡單介紹：PH是NP的外推，它包含NP類的所有問題，並在NP類問題的基礎上，添加了額外的複雜度。
詳細介紹：PH類包含一些交替使用比如「存在」、「每一個」、「所有」等「量詞」（quantifier）的問題，使NP類問題更加複雜。一個關於交替量詞問題的例子是：給定X，是否存在這樣的Y，使得對於每一個Z，都存在這樣的W，使得R成立？一個問題包含的量詞越多，它就越是複雜，在多項式層級結構中的排序也就越高。
典型問題：
- 確定是否存在規模為50的小團體，但不存在規模為51的小團體。
BPP
代表：有限錯誤概率多項式時間（Bounded-error Probabilistic Polynomial time）
簡單介紹：在多項式時間內，可以通過包含隨機性元素的演算法快速解決，且通常輸出結果的錯誤概率小於1/3的問題。
詳細介紹：BPP與P唯一不同的是，BPP的演算法允許包含隨機決策的步驟。BPP的演算法只需要以接近1的概率給出正確答案即可。
典型問題：
- 給定兩個不同的公式，每個公式產生一個包含很多變數的多項式，這兩個公式計算的是相同的多項式嗎？這個問題叫做多項式恆等檢驗問題。
研究人員想知道的是：BPP=P是否成立。如果這是真的，那就意味著每一個隨機性演算法都可以去隨機化。他們相信這是事實，因為對於每一個存在有效隨機性演算法的問題，都有一個有效的確定性演算法，但他們還不能證明這一點。
BQP
代表：有限錯誤量子多項式時間（Bounded-error Quantum Polynomial time）
簡單介紹：在多項式時間內，量子計算機能夠輕易解決的所有問題。
詳細介紹：在多項式時間內，量子計算機能夠輕易解決，且錯誤機率小於1/3的所有問題。
典型問題：
- 確定一個整數的質因數。
計算機科學家已經證明：PSPACE包含BQP，且BQP包含P。關於BQP和NP這兩個類的關係，有一些問題屬於NP類，而不屬於BQP類，反之亦然，兩者互不包含。
○計算複雜度地圖上一塊新區域：上文提到的五月底的研究，證明了存在屬於BQP，卻不屬於PH的問題。（註：P-經典計算機能夠快速解決的問題；NP-經典計算機就能夠驗證正確性的問題；NPC-NP完全問題；BQP-量子計算機能夠有效決的問題。）
QMA
代表：量子梅林亞瑟（Quantum Merlin Arthur）
簡單介紹：量子計算下的NP類問題。
詳細介紹：在量子計算下，如果給定 「是」的答案，在多項式時間內，能夠完成驗證，確定這個答案正確與否，這就是QMA類問題。QMA類問題相對於BQP類問題的關係，就相當於NP類問題相對於P類問題，也就是驗證與求解的複雜度的區別。
典型問題：
- 局部哈密頓量問題。
PSPACE
代表：多項式空間（Polynomial Space）
簡單介紹：PSPACE包含了所有隻要用合理大小的內存（多項式量級的內存）就能解決的問題。
詳細介紹：在PSPACE中，我們不關心時間，只關心運行演算法所需的內存。
典型問題：
- P、NP和PH類的所有問題都包含在PSPACE中。
計算機科學家已經證明，PSPACE包含PH，PH包含NP，NP包含P。然而，對於P是否等於NP，是否等於PH，是否等於PSPACE，計算機科學家始終一籌莫展。P=NP問題是克雷數學研究所發布的七道難題之一，可以進一步閱讀《一個價值百萬美金的問題》了解更多。
EXPTIME
代表：指數時間（EXPonential Time）
簡單介紹：在指數時間內，經典計算機能夠解決的所有問題。
詳細介紹：EXP包含之前所有的類——P、NP、PH、PSPACE、BQP和QMA等。研究人員已經證明，EXP不同於P，他們在EXP中發現了不屬於P的問題。
典型問題：
- 國際象棋和跳棋之類的遊戲都屬於EXP。如果棋盤可以是任意大小的，那麼在給定的棋局形勢下，確定哪一個棋手具有優勢就是一個EXP問題。
計算機科學家想要證明PSPACE不包含EXP。他們認為EXP中有一些問題不包含在PSPACE中，因為有時候EXP類問題的解決需要大量的內存。計算機科學家知道如何區分EXP和P。
在計算複雜度的地圖上，科學家們已經證明與尚未證明的問題可以總結如下：
從中可見，問題的源頭主要在於那個價值百萬美金的問題：P=NP是否成立。P是否等價NP的問題，可以簡化為NP完全問題的證明，也就是證明，是否能用多項式級複雜度的演算法來解決任何一個NP完全問題。
編譯：仔仔
審校：孫鵬
參考鏈接：
https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/
TAG:哲學園 |