Subclasses of Ptime Interpreted by Programming Languages
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Subclasses of Ptime Interpreted by Programming Languages. / Bhaskar, Siddharth; Kop, Cynthia; Simonsen, Jakob Grue.
In: Theory of Computing Systems, No. 3, 2023, p. 437-472.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Subclasses of Ptime Interpreted by Programming Languages
AU - Bhaskar, Siddharth
AU - Kop, Cynthia
AU - Simonsen, Jakob Grue
N1 - Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Abstract complexity theory
KW - Auxiliary pushdown automata
KW - Complexity theory
KW - Cons-free programs
KW - Lower bounds
U2 - 10.1007/s00224-022-10074-z
DO - 10.1007/s00224-022-10074-z
M3 - Journal article
AN - SCOPUS:85133191939
SP - 437
EP - 472
JO - Theory of Computing Systems
JF - Theory of Computing Systems
SN - 1432-4350
IS - 3
ER -
ID: 314302105