Bounded Analog Complexity
TL;DR
Bounded surrogate compilation is developed, a compilation framework that transforms unbounded polynomial ODE systems into bounded ones while preserving computational limits and time-to-precision guarantees.
Abstract
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 (wall-clock 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 if a system is compiled into a bounded system through our algorithm, the wall-clock time of the compiled system is polynomial in the arc length and physical time of the original system. We exhibit concrete constructions demonstrating fine-grained bounded time complexity -- a tunable polynomial-degree family, a Lambert-$W$-based system achieving $\Theta(r\log r)$ time-to-precision (where $r$ is the desired precision parameter, in nats: $|x(t)-\alpha|<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 ($\alpha^\beta$) 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.