Polynomial dynamics unify discrete and continuous computation models
One Polynomial Field for Every Euler Step and the Flow: Polynomial Dynamics for P and PSPACE
Computational ComplexityLogic in Computer Science
Summary
Computers usually work with step-by-step commands, like discrete steps, or with processes that change continuously over time. This paper shows how both kinds of computation can be represented using one kind of mathematical system called polynomial vector fields. The authors create a way to mimic the exact behavior of a computer running any algorithm, but within this smooth and continuous framework. This helps connect two different views of how machines compute, allowing better understanding of computational complexity classes like P and PSPACE through continuous mathematics.
What this means in practice
- •For complexity theorists: Use polynomial differential equations to analyze complexity classes like P and PSPACE in a unified computational framework.
- •For computational model designers: Design computational models that smoothly simulate discrete algorithms through continuous polynomial dynamics with robustness guarantees.
A theory result. No direct application yet.
Authors
Olivier Bournez
Abstract
We construct, for each deterministic Turing machine that halts on all inputs, one polynomial vector field with rational coefficients that performs the same logical computation at unit Euler step, at every smaller or variable step in $(0,1]$ with divergent sum, and along the flow. This unifies discrete-time and continuous-time computation by polynomial dynamics, which earlier characterizations treated separately. For a machine making $T$ transitions in space $H$, a logical scale $h=2^{-s}$ with $s=O(H)$ suffices, with physical time $O(s(T+s))$, drift disturbances up to $h^{2K}$ for a fixed exponent $K$, and $2Ks+3$ fractional bits at unit step. On a fixed compact domain, polynomial time and robust eventual decision characterize P and PSPACE, respectively, with polynomial scale thresholds and no supplied stabilization horizon in the space case. Without sign, floor or conditional primitives, margin amplification at bounded speed, overlapping polynomial gates and interval-product estimates give the common realization, from which we derive shared logical traces, fixed-field PSPACE-complete prediction and a robust safety family with polynomial certificates common to all Euler steps and the flow.