算法复杂性函数等价类A[F]中的分解性定理

DECOMPOSITION THEOREM IN ASYMPTOTICALLY DOMINATING EQUIVALENCE CLASSES OF COMPUTATIONAL COMPLEXITY FUNCTION

证明了算法复杂性函数渐近优超等价类数学结构A［F］中的分解性定理．对任意非免费算法复杂性函数类［f］∈A［F］及正整数n，存在类［g1］,［g2］,...,［gn］∈［F］满足［gi］＜［f］（i＝1，2，...，n）且［f］＝［gi］。

This paper proves that for any nonzero equivalence class [f] of A[F] and any positive integer n, there exist equivalence classes [g1], [g2], ..., [gn]∈[F] such that [gi]<[f] and [f]= [gi].