pith. machine review for the scientific record. sign in

arxiv: 2604.09790 · v1 · submitted 2026-04-10 · 💻 cs.CC

Recognition: no theorem link

Complexity Theory meets Ordinary Differential Equations

Adalbert Fono , Noah Wedlich , Holger Boche , Gitta Kutyniok
Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:44 UTC · model grok-4.3

classification 💻 cs.CC
keywords computational complexityordinary differential equationslinear systemscomplexity blowupTuring machine simulationanalog computingneuronal models
0
0 comments X

The pith

Linear ODEs of arbitrary order exhibit complexity blowup unless their algebraic properties meet specific degenerate conditions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that most linear ordinary differential equations cannot be simulated efficiently on digital computers. A low-complexity input signal, computable in polynomial time on a Turing machine, produces an output whose approximation to n significant digits requires superpolynomial time. This blowup is characterized exactly by algebraic properties of the ODE coefficients, extending earlier results that applied only to first-order equations. The same criterion is derived for certain first-order systems, and the framework is applied to a standard model of neuronal dynamics. If the characterization holds, it identifies a broad class of physical systems that resist efficient digital approximation.

Core claim

For linear ODEs of arbitrary order, complexity blowup occurs except in certain degenerate algebraic cases. The paper gives an exact algebraic criterion that determines whether a polynomial-time input forces superpolynomial time for high-precision output approximation, extending the first-order case and supplying an analogous criterion for a subclass of first-order linear systems.

What carries the argument

The algebraic characterization of complexity blowup, which classifies the ODE coefficients according to whether they induce a non-polynomial growth in the resources needed to approximate the solution from low-complexity inputs.

If this is right

  • Complexity blowup occurs for most linear ODEs of arbitrary order.
  • An analogous blowup criterion applies to a subclass of first-order linear systems.
  • Digital simulation of analog systems governed by such ODEs generally requires superpolynomial time.
  • The leaky integrate-and-fire neuron model exhibits the blowup in its standard formulation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • High-precision numerical integration routines for these ODEs cannot achieve polynomial scaling in precision.
  • The result separates systems whose continuous dynamics remain efficiently simulable from those that do not.
  • Engineering and neuroscience models relying on linear ODEs may need to adopt alternative approximation strategies or accept inherent precision limits.

Load-bearing premise

The inputs to the ODE are restricted to signals that are polynomial-time computable on a Turing machine.

What would settle it

An explicit non-degenerate linear ODE of order two or higher for which the solution at any fixed time can be approximated to n digits in time polynomial in n, given a polynomial-time input signal.

read the original abstract

This contribution investigates the computational complexity of simulating linear ordinary differential equations (ODEs) on digital computers. We provide an exact characterization of the complexity blowup for a class of ODEs of arbitrary order based on their algebraic properties, extending previous characterization of first order ODEs. Complexity blowup indeed arises in most ODEs (except for certain degenerate cases) and means that there exists a low complexity input signal, which can be generated on a Turing machine in polynomial time, leading to a corresponding high complexity output signal of the system in the sense that the computation time for determining an approximation up to $n$ significant digits grows faster than any polynomial in $n$. Similarly, we derive an analogous blowup criterion for a subclass of first-order systems of linear ODEs. Finally, we discuss the implications for the simulation of analog systems governed by ODEs and exemplarily apply our framework to a simple model of neuronal dynamics$-$the leaky integrate-and-fire neuron$-$heavily employed in neuroscience.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper investigates the computational complexity of simulating linear ordinary differential equations (ODEs) on digital computers. It claims an exact algebraic characterization of complexity blowup for linear ODEs of arbitrary order, based on properties of the characteristic polynomial and its roots (distinguishing degenerate vs. non-degenerate cases), extending prior first-order results. Inputs are polynomial-time computable signals in the sense of computable analysis; output complexity is measured by the time to approximate to n significant digits. An analogous criterion is derived for a subclass of first-order linear systems. The framework is applied to the leaky integrate-and-fire neuron model.

Significance. If the necessity and sufficiency of the algebraic criterion hold as stated, the result supplies a precise, checkable condition for when linear ODE simulation incurs superpolynomial blowup despite low-complexity inputs. This strengthens the link between computable analysis and complexity theory, with direct implications for reliable digital simulation of analog systems. The extension beyond first-order ODEs and the concrete neuroscience application increase its potential impact.

minor comments (3)
  1. Abstract: the claim that blowup 'arises in most ODEs (except for certain degenerate cases)' is informal; a brief parenthetical on how degeneracy is measured (e.g., via root multiplicity or algebraic independence) would improve precision without lengthening the abstract.
  2. The application to the leaky integrate-and-fire neuron is presented as an example rather than a core proof; ensure the section explicitly states that the model satisfies the non-degenerate algebraic condition and that the blowup prediction follows directly from the main theorem.
  3. Notation for the characteristic polynomial and its roots should be introduced once with a consistent symbol (e.g., p(λ)) and reused uniformly in the statements of the main theorems for arbitrary order and for the first-order system subclass.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our manuscript and for the positive assessment of its significance. The recommendation for minor revision is noted. No specific major comments were raised in the report, so we have no point-by-point rebuttals to provide. We will prepare a revised version incorporating any minor editorial improvements.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The manuscript establishes an exact algebraic characterization of complexity blowup for linear ODEs of arbitrary order by proving that a criterion on the characteristic polynomial (degenerate vs. non-degenerate roots) is both necessary and sufficient for the existence of polynomial-time inputs yielding superpolynomial output approximation time. This extends the first-order case via direct analysis rather than reduction to fitted parameters or prior self-referential results. Input signals are defined using standard computable-analysis notions and output complexity via Turing-machine time for n-digit approximations, with no hidden self-definition or smuggling of ansatzes. The leaky-integrate-and-fire application is presented separately and does not support the core equivalence. The derivation therefore stands as an independent proof within computability theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the central claim rests on standard assumptions from complexity theory and linear ODE theory; no free parameters, invented entities, or ad-hoc axioms are explicitly introduced.

axioms (1)
  • domain assumption Linear ODEs admit an algebraic classification that determines computational complexity blowup
    The paper states that blowup arises except in certain degenerate cases defined by algebraic properties.

pith-pipeline@v0.9.0 · 5473 in / 1125 out tokens · 23164 ms · 2026-05-10T15:44:29.596295+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 24 canonical work pages

  1. [1]

    A comparison by simulation and by measure- ment of the substrate noise generated by CMOS, CSL, and CBL digital circuits

    E.F.M. Albuquerque and M.M. Silva. “A comparison by simulation and by measure- ment of the substrate noise generated by CMOS, CSL, and CBL digital circuits”. In: IEEE Transactions on Circuits and Systems I: Regular Papers52.4 (2005), pp. 734– 741.doi:10.1109/TCSI.2005.844110

    work page doi:10.1109/tcsi.2005.844110 2005

  2. [2]

    Sanjeev Arora and Boaz Barak.Computational Complexity: A Modern Approach. 1st. USA: Cambridge University Press, 2009.isbn: 0521424267

    2009

  3. [3]

    A computer-aided test for the absence of limit cycles in fixed-point digital filters

    P.H. Bauer and L.-J. Leclerc. “A computer-aided test for the absence of limit cycles in fixed-point digital filters”. In:IEEE Transactions on Signal Processing39.11 (1991), pp. 2400–2410.doi:10.1109/78.97995

    work page doi:10.1109/78.97995 1991

  4. [4]

    Ef- ficient and Interpretable Deep Blind Image Deblurring Via Al- 26 Kojima et al. gorithm Unrolling

    Holger Boche and Ullrich J. Mönich. “Turing Computability of Fourier Transforms of Bandlimited and Discrete Signals”. In:IEEE Transactions on Signal Processing68 (2020), pp. 532–547.doi:10.1109/TSP.2020.2964204

    work page doi:10.1109/tsp.2020.2964204 2020

  5. [5]

    ComplexityBlowupinSimulatingAnalogLinearTime- Invariant Systems on Digital Computers

    HolgerBocheandVolkerPohl.“ComplexityBlowupinSimulatingAnalogLinearTime- Invariant Systems on Digital Computers”. In:IEEE Transactions on Signal Processing 69 (2021), pp. 5005–5020.doi:10.1109/TSP.2021.3102826. 23

    work page doi:10.1109/tsp.2021.3102826 2021

  6. [6]

    On the Algorithmic Solvability of the Spectral Factor- ization and the Calculation of the Wiener Filter on Turing Machines

    Holger Boche and Volker Pohl. “On the Algorithmic Solvability of the Spectral Factor- ization and the Calculation of the Wiener Filter on Turing Machines”. In:2019 IEEE International Symposium on Information Theory (ISIT). 2019, pp. 2459–2463.doi: 10.1109/ISIT.2019.8849557

    work page doi:10.1109/isit.2019.8849557 2019

  7. [7]

    Method for steady-state simulation of strongly nonlinear circuits in the time domain

    Angelo Brambilla and D. D’Amore. “Method for steady-state simulation of strongly nonlinear circuits in the time domain”. In:IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications48 (Aug. 2001), pp. 885–889.doi:10.1109/ 81.933329

    2001

  8. [8]

    K. E. Brenan, S. L. Campbell, and L. R. Petzold.Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations. Society for Industrial and Applied Math- ematics, 1995.doi:10.1137/1.9781611971224. eprint:https://epubs.siam.org/ doi/pdf/10.1137/1.9781611971224.url:https://epubs.siam.org/doi/abs/10. 1137/1.9781611971224

    work page doi:10.1137/1.9781611971224 1995

  9. [9]

    Out-of-Order Parallel Discrete Event Simulation for Transaction LevelModels

    Weiwei Chen et al. “Out-of-Order Parallel Discrete Event Simulation for Transaction LevelModels”.In:IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems33 (Dec. 2014), pp. 1859–1872.doi:10.1109/TCAD.2014.2356469

    work page doi:10.1109/tcad.2014.2356469 2014

  10. [10]

    2022 Roadmap on Neuromorphic Computing and Engineering

    Dennis Valbjørn Christensen et al. “2022 Roadmap on Neuromorphic Computing and Engineering”. In:Neuromorph. Comput. Eng.2.2 (2022). 022501

    2022

  11. [11]

    Effective Computability of Solutions of Ordinary Differential Equations The Thousand Monkeys Approach

    Pieter Collins and Daniel S. Graça. “Effective Computability of Solutions of Ordinary Differential Equations The Thousand Monkeys Approach”. en. In:Electronic Notes in Theoretical Computer Science221 (Dec. 2008), pp. 103–114.issn: 15710661.doi: 10 . 1016 / j . entcs . 2008 . 12 . 010.url:https : / / linkinghub . elsevier . com / retrieve/pii/S157106610800...

    2008

  12. [12]

    Cooper.Computability Theory

    S.B. Cooper.Computability Theory. 1st. New York, USA: Chapman and Hall/CRC, 2004

    2004

  13. [13]

    The Church-Turing Thesis

    B. Jack Copeland. “The Church-Turing Thesis”. In:The Stanford Encyclopedia of Phi- losophy. Ed. by Edward N. Zalta. Summer 2020. Metaphysics Research Lab, Stanford University, 2020

    2020

  14. [14]

    Lehrbücher und Monographien aus dem Gebiete der exakten Wissenschaften

    Gustav Doetsch.Handbuch der Laplace-Transformation: Band 3: Anwendungen der Laplace-Transformation. Lehrbücher und Monographien aus dem Gebiete der exakten Wissenschaften. Springer, Basel, 2014.isbn: 978-3-0348-5970-7

    2014

  15. [15]

    Sustainable AI: Mathematical Foundations of Spiking Neural Networks

    Adalbert Fono et al. “Sustainable AI: Mathematical Foundations of Spiking Neural Networks”. In:arXiv:2503.02013(2025)

    work page arXiv 2025

  16. [16]

    The computational complexity of maximization and integration

    Harvey Friedman. “The computational complexity of maximization and integration”. In:Advances in Mathematics53.1 (1984), pp. 80–98.issn: 0001-8708.doi:https : //doi.org/10.1016/0001-8708(84)90019-7.url:https://www.sciencedirect. com/science/article/pii/0001870884900197

    work page doi:10.1016/0001-8708(84)90019-7.url:https://www.sciencedirect 1984

  17. [17]

    Kistler.Spiking Neuron Models: Single Neurons, Populations, Plasticity

    Wulfram Gerstner and Werner M. Kistler.Spiking Neuron Models: Single Neurons, Populations, Plasticity. Cambridge University Press, 2002

    2002

  18. [18]

    Cambridge University Press, 2014

    Wulfram Gerstner et al.Neuronal Dynamics: From Single Neurons to Networks and Models of Cognition. Cambridge University Press, 2014. 24

    2014

  19. [19]

    Computability of Differential Equations

    Daniel S. GraÇa and Ning Zhong. “Computability of Differential Equations”. en. In: Handbook of Computability and Complexity in Analysis. Ed. by Vasco Brattka and Pe- ter Hertling. Series Title: Theory and Applications of Computability. Cham: Springer International Publishing, 2021, pp. 71–99.isbn: 978-3-030-59233-2 978-3-030-59234-9. doi:10.1007/978-3-030...

    work page doi:10.1007/978-3-030-59234-9_3.url:https://link.springer.com/10.1007/ 2021

  20. [20]

    FIRGEN: a computer-aided design system for high performance FIR filter integrated circuits

    R. Jain, P.T. Yang, and T. Yoshino. “FIRGEN: a computer-aided design system for high performance FIR filter integrated circuits”. In:IEEE Transactions on Signal Pro- cessing39.7 (1991), pp. 1655–1668.doi:10.1109/78.134402

    work page doi:10.1109/78.134402 1991

  21. [21]

    Computational Complexity in Analysis and Geometry

    Akitoshi Kawamura. “Computational Complexity in Analysis and Geometry”. PhD thesis. University of Toronto, 2011

    2011

  22. [22]

    Complexity Theory for Operators in Anal- ysis

    Akitoshi Kawamura and Stephen Cook. “Complexity Theory for Operators in Anal- ysis”. In:ACM Trans. Comput. Theory4.2 (2012).issn: 1942-3454.doi:10.1145/ 2189778.2189780.url:https://doi.org/10.1145/2189778.2189780

    work page doi:10.1145/2189778.2189780 2012

  23. [23]

    On the computational complexity of the Dirichlet Problem for Poisson’s Equation

    Akitoshi Kawamura, Florian Steinberg, and Martin Ziegler. “On the computational complexity of the Dirichlet Problem for Poisson’s Equation”. In:Mathematical Struc- tures in Computer Science27.8(2017),pp.1437–1465.doi:10.1017/S096012951600013X

    work page doi:10.1017/s096012951600013x 2017

  24. [24]

    Computational benefit of smoothness: Parameterized bit- complexity of numerical operators on analytic functions and Gevrey’s hierarchy

    Akitoshi Kawamura et al. “Computational benefit of smoothness: Parameterized bit- complexity of numerical operators on analytic functions and Gevrey’s hierarchy”. In: Journal of Complexity31.5 (2015), pp. 689–714.issn: 0885-064X.doi:https://doi. org / 10 . 1016 / j . jco . 2015 . 05 . 001.url:https : / / www . sciencedirect . com / science/article/pii/S08...

    2015

  25. [25]

    USA: Birkhauser Boston Inc., 1991

    Ker-I Ko.Complexity Theory of Real Functions. USA: Birkhauser Boston Inc., 1991

    1991

  26. [26]

    Computational complexity of real functions

    Ker-I. Ko and Harvey Friedman. “Computational complexity of real functions”. In: Theoretical Computer Science20.3 (1982), pp. 323–352.issn: 0304-3975.doi:https: //doi.org/10.1016/S0304-3975(82)80003-0.url:https://www.sciencedirect. com/science/article/pii/S0304397582800030

    work page doi:10.1016/s0304-3975(82)80003-0.url:https://www.sciencedirect 1982

  27. [27]

    Networks of spiking neurons: the third generation of neural network models

    Wolfgang Maass. “Networks of spiking neurons: the third generation of neural network models”. In:Neural networks10.9 (1997), pp. 1659–1671

    1997

  28. [28]

    On Polynomial Time Computable Numbers

    Tetsushi Matsui. “On Polynomial Time Computable Numbers”. In:arXiv:cs/0608067 (2006)

    work page arXiv 2006

  29. [29]

    Roadmap to neuromorphic computing with emerging tech- nologies

    Adnan Mehonic et al. “Roadmap to neuromorphic computing with emerging tech- nologies”. In:APL Materials12.10 (Oct. 2024), p. 109201.issn: 2166-532X.doi: 10 . 1063 / 5 . 0179424. eprint:https : / / pubs . aip . org / aip / apm / article - pdf / doi / 10 . 1063 / 5 . 0179424 / 20213999 / 109201 _ 1 _ 5 . 0179424 . pdf.url:https : //doi.org/10.1063/5.0179424

    work page doi:10.1063/5.0179424 2024

  30. [30]

    Differential/Algebraic Equations are not ODE’s

    Linda Petzold. “Differential/Algebraic Equations are not ODE’s”. In:SIAM Journal on Scientific and Statistical Computing3.3 (1982), pp. 367–384.doi:10.1137/0903023. eprint:https://doi.org/10.1137/0903023.url:https://doi.org/10.1137/ 0903023. 25

    work page doi:10.1137/0903023 1982

  31. [31]

    Pinter.A book of abstract algebra: 2nd edition

    Charles C. Pinter.A book of abstract algebra: 2nd edition. Dover Books on Mathemat- ics. Courier Corporation, 2010.isbn: 0486474178, 9780486474175

    2010

  32. [32]

    Pour-El and J

    Marian B. Pour-El and J. Ian Richards.Computability in Analysis and Physics. Per- spectives in Logic. Cambridge University Press, 2017

    2017

  33. [33]

    & Shepp, L

    Marian Boykan Pour-El and Ian Richards. “Noncomputability in analysis and physics: A complete determination of the class of noncomputable linear operators”. In:Advances in Mathematics48.1 (1983), pp. 44–74.issn: 0001-8708.doi:https://doi.org/10. 1016/0001- 8708(83)90004- X.url:https://www.sciencedirect.com/science/ article/pii/000187088390004X

    work page arXiv 1983

  34. [34]

    TheWaveEquationwithComputableInitialData Whose Unique Solution Is Nowhere Computable

    MarianB.Pour-ElandNingZhong.“TheWaveEquationwithComputableInitialData Whose Unique Solution Is Nowhere Computable”. In:Mathematical Logic Quarterly 43.4 (Nov. 2006), pp. 499–509.doi:10.1002/malq.19970430406.url:https://doi. org/10.1002/malq.19970430406

    work page doi:10.1002/malq.19970430406.url:https://doi 2006

  35. [35]

    Exploring Neuromorphic Computing Based on Spiking Neural Net- works: Algorithms to Hardware

    Nitin Rathi et al. “Exploring Neuromorphic Computing Based on Spiking Neural Net- works: Algorithms to Hardware”. In:ACM Comput. Surv.55.12 (2023)

    2023

  36. [36]

    On inconsistent initial conditions for linear time-invariant differential-algebraic equations

    Gunther Reißig, Holger Boche, and Paul I. Barton. “On inconsistent initial conditions for linear time-invariant differential-algebraic equations”. In:IEEE Trans. Circuits Sys- tems I Fund. Theory Appl.49.11 (2002), pp. 1646–1648.doi:10.1109/TCSI.2002. 804552

    work page doi:10.1109/tcsi.2002 2002

  37. [37]

    Evolutionarysynthesisoflow-sensitivity equalizers using adjacency matrix representation

    LeonardoBrunodeSáandAntonioMesquita.“Evolutionarysynthesisoflow-sensitivity equalizers using adjacency matrix representation”. In:Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. GECCO ’08. Atlanta, GA, USA:AssociationforComputingMachinery,2008,pp.1283–1290.isbn:9781605581309. doi:10 . 1145 / 1389095 . 1389342.url:https :...

    2008

  38. [38]

    Evolutionary Design of Digital Filters With Application to Subband Coding and Data Transmission

    Sancho Salcedo-Sanz et al. “Evolutionary Design of Digital Filters With Application to Subband Coding and Data Transmission”. In:IEEE Transactions on Signal Processing 55.4 (2007), pp. 1193–1203.doi:10.1109/TSP.2006.888883

    work page doi:10.1109/tsp.2006.888883 2007

  39. [39]

    Computability of the solutions to Navier-Stokes equations via effective approximation

    Shu Ming Sun, Ning Zhong, and Martin Ziegler. “Computability of the solutions to Navier-Stokes equations via effective approximation”. In:Complexity and Approxima- tion - In Memory of Ker-I Ko. Ed. by Ding-Zhu Du and Jie Wang. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatic...

    work page doi:10.1007/978-3-030-41672-0 2020

  40. [40]

    PP is as Hard as the Polynomial-Time Hierarchy

    Seinosuke Toda. “PP is as Hard as the Polynomial-Time Hierarchy”. In:SIAM Journal on Computing20.5 (1991), pp. 865–877.doi:10.1137/0220053. eprint:https:// doi.org/10.1137/0220053.url:https://doi.org/10.1137/0220053

    work page doi:10.1137/0220053 1991

  41. [41]

    On Computable Numbers, with an Application to the Entscheidungs- problem

    A. M. Turing. “On Computable Numbers, with an Application to the Entscheidungs- problem”. In:Proc. Lond. Math. Soc.s2-42.1 (1936), pp. 230–265. 26

    1936

  42. [42]

    Synthesis of low-sensitivity second-order digital filters using genetic programming with automatically defined functions

    Kazuyoshi Uesaka and M. Kawamata. “Synthesis of low-sensitivity second-order digital filters using genetic programming with automatically defined functions”. In:Signal Processing Letters, IEEE7 (May 2000), pp. 83–85.doi:10.1109/97.833004

    work page doi:10.1109/97.833004 2000

  43. [43]

    Berlin, Heidelberg: Springer- Verlag, 2000

    Klaus Weihrauch.Computable Analysis: An Introduction. Berlin, Heidelberg: Springer- Verlag, 2000

    2000

  44. [44]

    Is the Linear Schrödinger Propagator Turing Com- putable?

    Klaus Weihrauch and Ning Zhong. “Is the Linear Schrödinger Propagator Turing Com- putable?” In:Computability and Complexity in Analysis. Ed. by Jens Blanck, Vasco Brattka, and Peter Hertling. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 369–377.isbn: 978-3-540-45335-2. 27

    2001