2026-08-20T23:30:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20566 2024-08-23T05:50:28Z ddc:004 open_access

A New Characterization of FAC⁰ via Discrete Ordinary Differential Equations Antonelli, Melissa Durand, Arnaud Kontinen, Juha Implicit computational complexity parallel computation ordinary differential equations circuit complexity Implicit computational complexity is an active area of theoretical computer science, which aims at providing machine-independent characterizations of relevant complexity classes. One of the seminal works in this field appeared in 1965, when Cobham introduced a function algebra closed under bounded recursion on notation to capture FP. Later on, several complexity classes have been characterized using limited recursion schemas. In this context, a new approach was recently introduced, showing that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and providing a characterization of FP by an ODE-schema. The overall goal of the present work is precisely that of generalizing this approach to parallel computation, obtaining an original ODE-characterization for the small circuit classes FAC⁰ and FTC⁰. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Melissa Antonelli and Arnaud Durand and Juha Kontinen 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.10 urn:nbn:de:0030-drops-205664 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.10 eng https://creativecommons.org/licenses/by/4.0/legalcode