Subclasses of Ptime Interpreted by Programming Languages
Research output: Contribution to journal › Journal article › Research › peer-review
We consider the cons-free programming language of Neil Jones, a simple pure functional language, which decides exactly the polynomial-time relations and whose tail recursive fragment decides exactly the logarithmic-space relations. We exhibit a close relationship between the running time of cons-free programs and the running time of logspace-bounded auxiliary pushdown automata. As a consequence, we characterize intermediate classes like NC in terms of resource-bounded cons-free computation. In so doing, we provide the first “machine-free” characterizations of certain complexity classes, like P-uniform NC. Furthermore, we show strong polynomial lower bounds on cons-free running time. Namely, for every polynomial p, we exhibit a relation R ∈Ptime such that any cons-free program deciding R must take time at least p almost everywhere. Our methods use a “subrecursive version” of Blum complexity theory, and raise the possibility of further applications of this technology to the study of the fine structure of Ptime.
Original language | English |
---|---|
Journal | Theory of Computing Systems |
Issue number | 3 |
Pages (from-to) | 437-472 |
ISSN | 1432-4350 |
DOIs | |
Publication status | Published - 2023 |
Bibliographical note
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
- Abstract complexity theory, Auxiliary pushdown automata, Complexity theory, Cons-free programs, Lower bounds
Research areas
ID: 314302105