布魯姆測度亦稱複雜性測度或抽象複雜性測度.依布魯姆公理確定的一種抽象複雜性測度.設;;E,為一元部分遞歸函式列.
布魯姆測度亦稱複雜性測度或抽象複雜性測度.依布魯姆公理確定的一種抽象複雜性測度.設;;E,為一元部分遞歸函式列. 布魯姆測度(Blum measure)亦稱複雜性測度或抽象複雜性測度.依布魯姆公理確定的一種抽象複雜性測度...
布魯姆公理(Blum axioms)用以刻畫計算複雜性測度的兩條公理.它是由布魯姆(Blum , M.)於1967年引進的.設{}P,.};E。為全體一元部分遞歸函式的能行枚舉.}_ {};),E},為部分遞歸函式的一個序列. 布魯姆公理(Blum axioms)用以刻畫...
複雜性測度的稠密性(density of complexitymeasure)計算複雜性測度的一種性質.設中為一個布魯姆測度，F為一元遞歸函式集合.若對任何、，tEF，只要(s) C(t)，總存在uEF，使(s) C(u) C(t).則稱中在F上是稠密的.T-DSPACE在全...
複雜性測度的合適性(properness of complexi-y measure)計算複雜性測度的一種性質.設中-}};};E},為一個布魯姆測度.如果`di E c}(}為遞歸函式~};E}(}})).即只要複雜性函式中，本身是遞歸的，那么計算它自己的複雜性將不會...
仍是一個布魯姆測度，但它肯定不是有窮不變的(因為只要價。的一處變化，就會引起其複雜性的無窮變化).若中是具有有窮不變性的，則中一定是一致的，並且其複雜性類都是:。的，反之不然.通常所見的各種自然的複雜性測度都是具有有窮...
約定諸P是以自然數輸入的.那么其相應的複雜性測度便是一個函式列:a i Z…其中。(、)恰在式(n)收斂時有定義，而其值是算法式在輸入n後的計算複雜性度量(參見“布魯姆測度”). _ ; 。二便是一種計算複雜性測度.其中的每個...
相關性定理(related ness theorem)反映複雜性測度間關係的一個重要結論。具體地說，任何兩個布魯姆測度中和少都是遞歸相關的.也即存在遞歸 在遞歸因子之下，所有的計算複雜性測度都是“漸近地相同的”.換言之，如果一個函式對某個計算...
純正函式 純正函式(honest f unction)一種特殊的部分遞歸函式.這種函式的值可以“反映”其複雜性.具體地說，設f為一元部分遞歸函式，g為二元遞歸函式，中是一個布魯姆測度，若存在f的一個下標i，使得 b}.e}+r ...
