布盧姆公理

布魯姆公理（英語：Blum Axioms），或稱布魯姆複雜度公理（英語：Blum Complexity Axioms），是計算複雜性理論中，定義可計算函數的複雜度時，應滿足的條件。這些公理最先由曼紐爾·布魯姆於1967年提出。^[1]

重要的是，只要複雜度衡量滿足這些公理，布盧姆加速定理和間隙定理就成立。滿足這些公理的複雜度衡量裡，最有名的是有關時間（見時間複雜度）和空間（見空間複雜度）的複雜度。

定義

布魯姆複雜度衡量是一個二元組${\displaystyle (\varphi ,\Phi )}$ ，其中${\displaystyle \varphi }$ 是偏可計算函數集${\displaystyle \mathbf {P} ^{(1)}}$ 的哥德爾編號，而${\displaystyle \Phi :\mathbb {N} \to \mathbf {P} ^{(1)}}$ 是一個可計算函數，滿足以下的布魯姆公理。用${\displaystyle \varphi _{i}}$ 表示哥德爾編號${\displaystyle \varphi }$ 下的第i個偏可計算函數，${\displaystyle \Phi _{i}}$ 表示偏可計算函數${\displaystyle \Phi (i)}$ 。

1. 函數${\displaystyle \varphi _{i}}$ 和${\displaystyle \Phi _{i}}$ 的定義域相同。
2. 集合${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}}$ 是遞歸的。

例子

在定義中，${\displaystyle \Phi _{i}(x)}$ 應當理解成${\displaystyle i}$ 所編碼的計算過程，在輸入為${\displaystyle x}$ 時，所消耗的資源（例如時間、空間，或兩者的適當組合）。

• 若${\displaystyle \Phi }$ 測量時間，則${\displaystyle (\varphi ,\Phi )}$ 是複雜度衡量：需要的時間或計算量可計算，因為可以直接模擬。而第二條公理也成立，因為要判斷${\displaystyle \Phi _{i}(x)=t}$ 是否成立，只需運行至多${\displaystyle t}$ 步，所以總能在有限時間內判斷。
• 若${\displaystyle \Phi }$ 測量空間（記憶體），則${\displaystyle (\varphi ,\Phi )}$ 亦為複雜度衡量，但原因較時間複雜：當限制空間為${\displaystyle t}$ 時，整個系統的可能狀態只有有限多個（例如若圖靈機有${\displaystyle q}$ 個狀態，其紙帶有${\displaystyle s}$ 種符號，則紙帶共只有${\displaystyle s^{t}}$ 種可能性，最後乘上讀寫頭位置的${\displaystyle t}$ 種可能性，整個系統只有${\displaystyle qs^{t}t}$ 種可能性）。從而，只要模擬足夠長的時間，必有以下三者之一：
  • 計算結束；
  • 整個系統重複某個狀態，受困於無窮迴圈；
  • 超出空間限制${\displaystyle t}$ 。

所以，在有限時間內，可以判斷${\displaystyle \Phi _{i}(x)=t}$ 是否成立。

• 作為反例，${\displaystyle (\varphi ,\varphi )}$ 並非一個複雜度衡量，因為其不滿足第二條公理。

與計算模型的關係

布盧姆的複雜度定義不取決於具體的計算模型，但也可以圖靈機的用語複述一次，幫助理解。

布魯姆複雜度衡量是將二元組（圖靈機${\displaystyle M}$ ，輸入${\displaystyle x}$ ）射去自然數或${\displaystyle \infty }$ 的映射${\displaystyle \Phi }$ ，其滿足以下公理（對應前述定義）：

1. ${\displaystyle \Phi (M,x)}$ 為${\displaystyle \infty }$ 當且僅當${\displaystyle M(x)}$ 不停機。
2. 有算法可以判斷，當輸入${\displaystyle (M,x,t)}$ 時，是否有${\displaystyle \Phi (M,x)=t}$ 。

例如，${\displaystyle \Phi (M,x)}$ 可以是${\displaystyle M}$ 輸入${\displaystyle x}$ 時運行至停機所需的步數。按定義可知第一條公理成立。而且，用通用圖靈機模擬${\displaystyle M}$ 輸入${\displaystyle x}$ 並運行${\displaystyle t}$ 步，就是滿足第二條公理條件的算法。

複雜度類

對於全可計算函數${\displaystyle f}$ ，可計算函數的複雜度類可定義成

${\displaystyle C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\},}$ 

${\displaystyle C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}.}$ 

${\displaystyle C(f)}$ 是所有複雜度小於${\displaystyle f}$ 的可計算函數構成的集合。${\displaystyle C^{0}(f)}$ 是複雜度比${\displaystyle f}$ 小的布爾函數集合。若我們視這些函數為集合的指示函數，則可視${\displaystyle C^{0}(f)}$ 為集合的複雜度類。

參考文獻

1. Blum, Manuel. A Machine-Independent Theory of the Complexity of Recursive Functions (PDF). ACM期刊. 1967, 14 (2): 322–336 [2021-08-09]. doi:10.1145/321386.321395. （原始内容 (PDF)于2016-01-15）.