A Characterization of Space Complexity Cases and Subexponential Time Classesas Limiting Polynomially Decidable Sets
| Title | A Characterization of Space Complexity Cases and Subexponential Time Classesas Limiting Polynomially Decidable Sets |
| Publication Type | Technical Report |
| Year of Publication | 1991 |
| Authors | Ausiello, G., Protasi M., & Angelaccio M. |
| Other Numbers | 676 |
| Abstract | The concept of limiting approximation, originally introduced by Gold for recursive functions, has been previously adapted by the authors to the polynomial level of complexity in order to study complexity classes of sets polynomially computable in the limit. In this paper new results concerning the characterization of space complexity classes (from PSPACE to Grzegorczyk classes) as classes of sets polynomially decidable in the limit are presented. Besides tight trade-offs between the rate of convergence of the approximating sequences and the constants of their polynomially running time are shown. Finally the limiting polynomial approximation for classes of sets between P and PSPACE is investigated under the hypothesis that P is different from PSPACE. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-91-046.pdf |
| Bibliographic Notes | ICSI Technical Report TR-91-046 |
| Abbreviated Authors | G. Ausiello, M. Protasi, and M. Angelaccio |
| ICSI Publication Type | Technical Report |