跳转到内容

布盧姆公理

维基百科,自由的百科全书

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

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

定義

[编辑]

布魯姆複雜度衡量是一個二元組,其中偏可計算函數集哥德爾編號,而是一個可計算函數,滿足以下的布魯姆公理。用表示哥德爾編號下的第i偏可計算函數表示偏可計算函數

  1. 函數定義域相同。
  2. 集合遞歸的

例子

[编辑]

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

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

與計算模型的關係

[编辑]

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

布魯姆複雜度衡量是將二元組(圖靈機,輸入)射去自然數或的映射,其滿足以下公理(對應前述定義):

  1. 當且僅當停機
  2. 有算法可以判斷,當輸入時,是否有

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

複雜度類

[编辑]

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

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

參考文獻

[编辑]
  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).