Back to Search
Start Over
Characterizing polynomial and exponential complexity classes in elementary lambda-calculus.
- Source :
-
Information & Computation . Aug2018:Part 1, Vol. 261, p55-77. 23p. - Publication Year :
- 2018
-
Abstract
- In this paper an implicit characterization of the complexity classes k - EXP and k - FEXP , for k ≥ 0 , is given, by a type assignment system for a stratified λ -calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic ( ELL ), and the hierarchy of complexity classes k - EXP is characterized by a hierarchy of types. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIALS
*CALCULUS
*LAMBDA meson
*ALGORITHMS
*COMPLEXITY (Philosophy)
Subjects
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 261
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 130046681
- Full Text :
- https://doi.org/10.1016/j.ic.2018.05.005