2026-07-27T10:08:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26784 2026-07-27T07:33:58Z ddc:004 open_access

Bounded Analog Complexity Chen, Ho-Lin Huang, Xiang Analog computation GPAC bounded complexity chemical reaction networks polynomial ODE Current analog complexity theory, built on the General-Purpose Analog Computer (GPAC) model and polynomial ODEs, allows unbounded state variables - an assumption that is physically unrealistic for chemical reaction networks and other laboratory-scale analog computers. We develop a bounded analog complexity theory in which all state variables remain in compact intervals and physical time is the only diverging resource. Our main technical contribution is bounded surrogate compilation, a compilation framework that transforms unbounded polynomial ODE systems into bounded ones while preserving computational limits and time-to-precision guarantees. We prove that on compact domains, physical time and trajectory length differ by at most constant factors; combined with the Bournez-Graça-Pouly characterization, this yields: bounded-GPAC polynomial time equals 𝐏 over the reals. We exhibit concrete constructions demonstrating fine-grained bounded time complexity - a tunable polynomial-degree family, a Lambert-W-based system achieving Θ(rlog r) time-to-precision (where r is the desired precision parameter, in nats: |x(t)-α| < e^{-r}), and an iterated-logarithm tower realizing arbitrarily high complexity classes - all for the task of computing the constant 1. We show that bounded GPACs are closed under exponentiation (α^β) with time complexity equal to the harder input, and that the full GPAC-to-CRN compilation pipeline preserves time complexity class via a low-pass filter analysis of readout modules. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ho-Lin Chen and Xiang Huang 2026 Is Part Of LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DNA.32.14 urn:nbn:de:0030-drops-267841 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.14 eng https://creativecommons.org/licenses/by/4.0/legalcode