| 摘要: |
| 本文建立了算法复杂性函数渐近优超等价类数学结构,并应用递归论研究中的方法和技巧对该结构的性质进行了系统的研究,证明了该结构具有强Friedberg-Muchnic性质和在偏序意义下的稠密性定理. |
| 关键词: 算法复杂性,渐近优超. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家863高科技项目基金资助. |
|
| Structure Properties about Asymptotically Dominating Equivalence Classes of Computational Complexity Functions |
|
ZHANG Zai-yue
|
| Abstract: |
| In this paper, the authors established a mathematical structure of asymptotically dominating equivalence classes of computational complexity functions and studied the properties of the structure systematically. Applying the methods and techniques of recursion theory to the study of this structure, they proved that the structure has strongly Friedberg-Muchnic property and is dense under the sense of partial ordering. |
| Key words: Computational complexity, asymptotically dominating. |
