Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length

Article, Preprint English OPEN
Bournez, Olivier; Graça, Daniel S.; Pouly, Amaury; (2016)
  • Publisher: Association for Computing Machinery
  • Journal: Journal of the ACM,volume 64,issue 6,pages1-76 (issn: 00045411)
  • Related identifiers: doi: 10.4230/LIPIcs.ICALP.2016.109, doi: 10.1145/3127496
  • Subject: Theory of computation | Mathematics of computing | Computing methodologies | Computer systems organization | Computer Science - Computational Complexity

The outcomes of this article are twofold. Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class P of languages computable in polynomial time in terms of diff... View more
Share - Bookmark