One Polynomial Field for Every Euler Step and the Flow: Polynomial Dynamics for P and PSPACE
cs.CC, cs.LO, math.DS
Submitted: 2026-10-29
Updated: 2026-11-02
Comments: 93 pages. Ancillary files: exact local checks (Python 3, standard library only). v2: explicit horizon in Corollary 55, minor corrections
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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…
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.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?