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

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

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

函數\varphi_i和\Phi_i的定義域相同。

集合\{(i,x,t) \in \mathbb{N}^3 | \Phi_i(x) = t\}是遞歸的。

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

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

** 計算結束；
** 整個系統重複某個狀態，受困於無窮迴圈；
** 超出空間限制t。
: 所以，在有限時間內，可以判斷\Phi_i(x) = t是否成立。

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

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

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

\Phi(M, x)為\infty當且僅當M(x)不停機。

有算法可以判斷，當輸入(M, x, t)時，是否有\Phi(M, x) = t。

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

複雜度類
對於全可計算函數f，可計算函數的複雜度類可定義成
:C(f) := \{ \varphi_i \in \mathbf{P}^{(1)} | \forall x.\ \Phi_i(x) \leq f(x) \},
:C^0(f) := \{ h \in C(f) | \mathrm{codom}(h) \subseteq \{0,1\} \}.

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

參考文獻