算法复杂性函数等价类AF中的分解性定理

摘要

证明了算法复杂性函数渐近优超等价类数学结构Ａ［Ｆ］中的分解性定理。对任意非免费算法复杂性函数类［ｆ］∈Ａ［Ｆ］及正整数ｎ，存在类［ｇ１］，［ｇ２］，…，［ｇｎ］∈Ａ［Ｆ］满足［ｇｉ］〈［ｆ］（ｉ＝１，２，…，ｎ）且［ｆ］＝Ｖｉ＝１＾ｎ［ｇｉ］。