The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Fine Separation of Average-Time Complexity Classes
Jin-Yi Cai, Alan L. Selman,
Pages. 1310-1325
Abstract
Contents 1. Introduction
2. Preliminaries
2.1. Turing machine running times
2.2. Distributional problems
2.3. Hardy's class of logarithmico-exponential functions
3. The first hierarchy theorem
3.1. Inadequacy of definition 3.1
3.2. First hierarchy theorem
4. The new definition and second hierarchy theorem
4.1. Equivalence theorem
4.2. Second hierarchy theorem
4.3. Pathological distributions
4.4. Final comments
5. Random-access machines
Key words computational complexity, average-time complexity classes, hierarchy, Average-P, logarithmico-exponential functions
Mathmatical Subject Classification 68Q10, 68Q15