布盧姆公理

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

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

 定義 

布魯姆複雜度衡量是一個二元組，其中是偏可計算函數集的哥德爾編號，而是一個可計算函數，滿足以下的布魯姆公理。用表示哥德爾編號下的第i個偏可計算函數，表示偏可計算函數。
 函數和的定義域相同。
 集合是遞歸的。

 例子 

在定義中，應當理解成所編碼的計算過程，在輸入為時，所消耗的資源（例如時間、空間，或兩者的適當組合）。
 若測量時間，則是複雜度衡量：需要的時間或計算量可計算，因為可以直接模擬。而第二條公理也成立，因為要判斷是否成立，只需運行至多步，所以總能在有限時間內判斷。
 若測量空間（記憶體），則亦為複雜度衡量，但原因較時間複雜：當限制空間為時，整個系統的可能狀態只有有限多個（例如若圖靈機有個狀態，其紙帶有種符號，則紙帶共只有種可能性，最後乘上讀寫頭位置的種可能性，整個系統只有種可能性）。從而，只要模擬足夠長的時間，必有以下三者之一：
 計算結束；
 整個系統重複某個狀態，受困於無窮迴圈；
 超出空間限制。
 所以，在有限時間內，可以判斷是否成立。
 作為反例，並非一個複雜度衡量，因為其不滿足第二條公理。

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

布魯姆複雜度衡量是將二元組（圖靈機，輸入）射去自然數或的映射，其滿足以下公理（對應前述定義）：
 為當且僅當不停機。
 有算法可以判斷，當輸入時，是否有。

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

 複雜度類 

對於全可計算函數，可計算函數的複雜度類可定義成

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

 參考文獻 

Category:結構複雜度理論
Category:公理