Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.23805 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911709240754176 |
|---|---|
| author | Antonelli, Melissa Durand, Arnaud Li, Rui |
| author_facet | Antonelli, Melissa Durand, Arnaud Li, Rui |
| contents | The paper proposes an implicit (i.e., machine-independent) complexity approach to studying computation by polynomial-size, constant-depth circuits with gates counting modulo a constant through the lens of discrete ordinary differential equations (ODEs). So far, recursion-theoretic characterizations have been provided for functions computed by circuits of constant depth, including gates counting modulo 2 and 6 only (i.e., for the classes FAC0[2] and FAC0[6], resp.). In this paper, it is shown that considering ODE schemas, rather than bounded recursion, allows for a more fine-grained analysis, leading to (uniform) characterizations for all classes FAC0[n] (n \in N), i.e. functions computed by circuits including counting modulo n gates. Inspired by the syntactic form of the ODE schemas, we go further in this direction and present first-order bounded theories for capturing provably total functions in each of these classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_23805 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version) Antonelli, Melissa Durand, Arnaud Li, Rui Computational Complexity The paper proposes an implicit (i.e., machine-independent) complexity approach to studying computation by polynomial-size, constant-depth circuits with gates counting modulo a constant through the lens of discrete ordinary differential equations (ODEs). So far, recursion-theoretic characterizations have been provided for functions computed by circuits of constant depth, including gates counting modulo 2 and 6 only (i.e., for the classes FAC0[2] and FAC0[6], resp.). In this paper, it is shown that considering ODE schemas, rather than bounded recursion, allows for a more fine-grained analysis, leading to (uniform) characterizations for all classes FAC0[n] (n \in N), i.e. functions computed by circuits including counting modulo n gates. Inspired by the syntactic form of the ODE schemas, we go further in this direction and present first-order bounded theories for capturing provably total functions in each of these classes. |
| title | Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version) |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2605.23805 |