布魯姆公理(英語:Blum Axioms),或稱布魯姆複雜度公理(英語:Blum Complexity Axioms),是計算複雜性理論中,定義可計算函數的複雜度時,應滿足的條件。這些公理最先由曼紐爾·布魯姆於1967年提出。[1]
重要的是,只要複雜度衡量滿足這些公理,布盧姆加速定理和間隙定理就成立。滿足這些公理的複雜度衡量裡,最有名的是有關時間(見時間複雜度)和空間(見空間複雜度)的複雜度。
布魯姆複雜度衡量是一個二元組
,其中
是偏可計算函數集
的哥德爾編號,而
是一個可計算函數,滿足以下的布魯姆公理。用
表示哥德爾編號
下的第i個偏可計算函數,
表示偏可計算函數
。
- 函數
和
的定義域相同。
- 集合
是遞歸的。
在定義中,
應當理解成
所編碼的計算過程,在輸入為
時,所消耗的資源(例如時間、空間,或兩者的適當組合)。
- 若
測量時間,則
是複雜度衡量:需要的時間或計算量可計算,因為可以直接模擬。而第二條公理也成立,因為要判斷
是否成立,只需運行至多
步,所以總能在有限時間內判斷。
- 若
測量空間(記憶體),則
亦為複雜度衡量,但原因較時間複雜:當限制空間為
時,整個系統的可能狀態只有有限多個(例如若圖靈機有
個狀態,其紙帶有
種符號,則紙帶共只有
種可能性,最後乘上讀寫頭位置的
種可能性,整個系統只有
種可能性)。從而,只要模擬足夠長的時間,必有以下三者之一:
- 計算結束;
- 整個系統重複某個狀態,受困於無窮迴圈;
- 超出空間限制
。
- 所以,在有限時間內,可以判斷
是否成立。
- 作為反例,
並非一個複雜度衡量,因為其不滿足第二條公理。
與計算模型的關係[编辑]
布盧姆的複雜度定義不取決於具體的計算模型,但也可以圖靈機的用語複述一次,幫助理解。
布魯姆複雜度衡量是將二元組(圖靈機
,輸入
)射去自然數或
的映射
,其滿足以下公理(對應前述定義):
為
當且僅當
不停機。
- 有算法可以判斷,當輸入
時,是否有
。
例如,
可以是
輸入
時運行至停機所需的步數。按定義可知第一條公理成立。而且,用通用圖靈機模擬
輸入
並運行
步,就是滿足第二條公理條件的算法。
複雜度類[编辑]
對於全可計算函數
,可計算函數的複雜度類可定義成
![{\displaystyle C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7223171a61d02ea26987562b8e6611b4c21eb9f7)
![{\displaystyle C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfbc5c30b80b49ddc85ab50d0453c1c0a3009286)
是所有複雜度小於
的可計算函數構成的集合。
是複雜度比
小的布爾函數集合。若我們視這些函數為集合的指示函數,則可視
為集合的複雜度類。
參考文獻[编辑]