Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916920511430656 |
|---|---|
| author | Antonelli, Melissa Durand, Arnaud Kontinen, Juha |
| author_facet | Antonelli, Melissa Durand, Arnaud Kontinen, Juha |
| contents | Implicit computational complexity is a lively area of theoretical computer science, which aims to provide machine-independent characterizations of relevant complexity classes. % for uniformity with subsequent uses >> 1960s (but feel free to modify it) % One of the seminal works in this field appeared in the 1960s, when Cobham introduced a function algebra closed under bounded recursion on notation to capture polynomial time computable functions ($FP$). Later on, several complexity classes have been characterized using \emph{limited} recursion schemas. In this context, an original approach has been recently introduced, showing that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and providing a characterization of $FP$ by a new ODE-schema. In the present paper we generalize this approach by presenting original ODE-characterizations for the small circuit classes $AC^0$ and $FTC^0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19392 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations Antonelli, Melissa Durand, Arnaud Kontinen, Juha Computational Complexity F.1.3; F.2.3 Implicit computational complexity is a lively area of theoretical computer science, which aims to provide machine-independent characterizations of relevant complexity classes. % for uniformity with subsequent uses >> 1960s (but feel free to modify it) % One of the seminal works in this field appeared in the 1960s, when Cobham introduced a function algebra closed under bounded recursion on notation to capture polynomial time computable functions ($FP$). Later on, several complexity classes have been characterized using \emph{limited} recursion schemas. In this context, an original approach has been recently introduced, showing that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and providing a characterization of $FP$ by a new ODE-schema. In the present paper we generalize this approach by presenting original ODE-characterizations for the small circuit classes $AC^0$ and $FTC^0$. |
| title | Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations |
| topic | Computational Complexity F.1.3; F.2.3 |
| url | https://arxiv.org/abs/2508.19392 |