計算複雜性理論是研究解決計算問題所需資源的學科。它提供了一個分析演算法效率的框架,在運算能力與資料儲存日益重要的時代,這一議題愈發關鍵。此學科的核心目標,在於理解計算問題的固有難度以及高效計算的限制。

時間、空間與 Big O 表示法

計算複雜性理論的基礎,在於演算法解決問題所需的時間與空間。時間複雜度指演算法完成所需的步驟數,空間複雜度則指其所使用的記憶體量。這兩項指標是評估演算法效率的根本,通常以 Big O 表示法表達,即對所需步驟數或空間量給出上界。由於 Big O 描述的是資源用量相對於輸入規模的成長方式,而非在特定硬體上的原始速度,因此可以在不受機器影響的情況下比較不同演算法。

P 與 NP:基本類別

計算複雜性理論中最重要的兩個類別是 P(多項式時間,Polynomial Time 的縮寫)與 NP(非確定性多項式時間,Nondeterministic Polynomial Time 的縮寫)。P 包含可由確定性圖靈機在多項式時間內求解的決策問題,亦即其執行時間至多隨輸入規模呈多項式成長。相對地,NP 包含這樣一類決策問題:確定性圖靈機可在多項式時間內驗證一個建議解,但該解本身未必能被快速找到。

P 是否等於 NP,是電腦科學中最深奧的未解問題之一。若 P=NP,則每個具有已知高效驗證方法的問題,也存在找到解的高效演算法。若 P≠NP,則存在某些問題,即使其解可以被高效驗證,也不存在高效的求解演算法。此問題的重要性,體現於其被列為克雷數學研究所設立的七道千禧年大獎難題之一,每道難題的解答可獲得 100 萬美元獎金。此問題的解答對密碼學、最佳化問題以及科學與工程的諸多領域都有重大影響,因為現代密碼學的很大一部分,正建立在某些問題在實際時間內無法被攻擊者破解的假設之上。

歸約與 NP 完全性

證明問題困難度的關鍵概念是歸約,即將一個問題轉換為另一個問題。若問題 A 可歸約為問題 B,且 B 已知是困難的,則 A 至少與 B 同等困難。NP 完全問題是指那些至少與 NP 中最難問題同等困難的問題。若任何 NP 完全問題被找到多項式時間解,則 P=NP。著名的 NP 完全問題包括旅行推銷員問題、布林可滿足性問題(SAT)與背包問題。這類問題絕非純粹的學術議題:它們經常出現在路由、排程與資源分配中;在缺乏高效精確演算法的情況下,實務上通常改用近似演算法與啟發式方法,以放棄保證最佳解來換取可接受的執行時間。

計算複雜性理論為理解演算法效率的微妙之處與計算的極限提供了豐富的框架。透過 P、NP 與歸約的視角,研究人員得以洞見高效解決複雜問題的根本挑戰。隨著運算在日常生活中扮演愈來愈重要的角色,計算複雜性理論的研究依然至關重要,引導我們走向更高效的解法,並闡明可計算範圍的邊界。在 P 與 NP 問題獲得解答之前,已知存在高效解的問題與尚未找到高效解的問題之間的分界線,將持續影響研究優先順序與工程實務。

來源:OPEC