查看“︁布盧姆公理”︁的源代码

'''布魯姆公理'''（英語：Blum Axioms），或稱'''布魯姆複雜度公理'''（英語：Blum Complexity Axioms），是[[計算複雜性理論]]中，定義[[可計算函數]]的複雜度時，應滿足的條件。這些公理最先由[[曼紐爾·布盧姆|曼紐爾·布魯姆]]於1967年提出。<ref>{{Cite journal | last = Blum | first = Manuel | authorlink = 曼紐爾·布盧姆 | title = A Machine-Independent Theory of the Complexity of Recursive Functions | doi = 10.1145/321386.321395 | journal = [[ACM期刊]] | volume = 14 | issue = 2 | pages = 322–336 | year = 1967 | url = http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf | access-date = 2021-08-09 | archive-date = 2016-01-15 | archive-url = https://web.archive.org/web/20160115171146/http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf | dead-url = no }}</ref>

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

== 定義 ==

'''布魯姆複雜度衡量'''是一個二元組<math>(\varphi, \Phi)</math>，其中<math>\varphi</math>是[[可計算函數|偏可計算函數集]]<math>\mathbf{P}^{(1)}</math>的[[編號 (計算理論)|哥德爾編號]]，而<math>\Phi: \mathbb{N} \to \mathbf{P}^{(1)}</math>是一個[[可計算函數]]，滿足以下的'''布魯姆公理'''。用<math>\varphi_i</math>表示哥德爾編號<math>\varphi</math>下的第''i''個[[可計算函數|偏可計算函數]]，<math>\Phi_i</math>表示偏可計算函數<math>\Phi(i)</math>。
# 函數<math>\varphi_i</math>和<math>\Phi_i</math>的[[定義域]]相同。
# 集合<math>\{(i,x,t) \in \mathbb{N}^3 | \Phi_i(x) = t\}</math>是[[遞歸語言|遞歸的]]。

== 例子 ==

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

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

'''布魯姆複雜度衡量'''是將二元組（圖靈機<math>M</math>，輸入<math>x</math>）射去自然數或<math>\infty</math>的映射<math>\Phi</math>，其滿足以下公理（對應[[#定義|前述定義]]）：
# <math>\Phi(M, x)</math>為<math>\infty</math>[[當且僅當]]<math>M(x)</math>不[[停機問題|停機]]。
# 有算法可以判斷，當輸入<math>(M, x, t)</math>時，是否有<math>\Phi(M, x) = t</math>。

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

== 複雜度類 ==

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

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

== 參考文獻 ==

{{Reflist}}

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