About: ブラムの公理

計算複雑性理論におけるブラムの公理（ブラムのこうり、英: Blum axioms）またはブラムの複雑性公理とは、計算可能関数の集合上の複雑性測度の満たすべき性質を述べた公理である。この公理はマヌエル・ブラムによって1967年に導入された。 重要な結果として、公理を満たす任意の複雑性測度でブラムの加速定理とギャップ定理が成り立つことが知られる。公理を満たす測度として最もよく知られているものとしては時間複雑性と空間複雑性がある。