{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T20:57:42Z","timestamp":1775077062764,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T00:00:00Z","timestamp":1507075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia and EU FEDER POCTI\/POCI via SQIG - Instituto de Telecomunica\u00e7\u00f5es through the FCT project","award":["UID\/EEA\/50008\/2013"],"award-info":[{"award-number":["UID\/EEA\/50008\/2013"]}]},{"name":"DGA Project CALCULS and French National Research Agency (ANR) Project","award":["ANR-15-CE040-0016-01 RACAF"],"award-info":[{"award-number":["ANR-15-CE040-0016-01 RACAF"]}]},{"name":"European Unions Horizon 2020 research"},{"name":"Marie Sk\u0142odowska-Curie","award":["731143"],"award-info":[{"award-number":["731143"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>The outcomes of this article are twofold.<\/jats:p>\n          <jats:p>\n            <jats:bold>Implicit complexity.<\/jats:bold>\n            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 differential equations with polynomial right-hand side. This result gives a purely continuous elegant and simple characterization of P. We believe it is the first time complexity classes are characterized using only ordinary differential equations. Our characterization extends to functions computable in polynomial time over the reals in the sense of Computable Analysis.\n          <\/jats:p>\n          <jats:p>Our results may provide a new perspective on classical complexity, by giving a way to define complexity classes, like P, in a very simple way, without any reference to a notion of (discrete) machine. This may also provide ways to state classical questions about computational complexity via ordinary differential equations.<\/jats:p>\n          <jats:p>\n            <jats:bold>Continuous-Time Models of Computation.<\/jats:bold>\n            Our results can also be interpreted in terms of analog computers or analog models of computation: As a side effect, we get that the 1941 General Purpose Analog Computer (GPAC) of Claude Shannon is provably equivalent to Turing machines both in terms of computability and complexity, a fact that has never been established before. This result provides arguments in favour of a generalised form of the Church-Turing Hypothesis, which states that any physically realistic (macroscopic) computer is equivalent to Turing machines both in terms of computability and complexity.\n          <\/jats:p>","DOI":"10.1145\/3127496","type":"journal-article","created":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T12:17:29Z","timestamp":1507119449000},"page":"1-76","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length"],"prefix":"10.1145","volume":"64","author":[{"given":"Olivier","family":"Bournez","sequence":"first","affiliation":[{"name":"Ecole Polytechnique, LIX"}]},{"given":"Daniel S.","family":"Gra\u00e7a","sequence":"additional","affiliation":[{"name":"Universidade do Algarve and Instituto de Telecomunica\u00e7\u00f5e"}]},{"given":"Amaury","family":"Pouly","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique, LIX and Department of Computer Science, University of Oxford"}]}],"member":"320","published-online":{"date-parts":[[2017,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032042"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0885-064X(03)00032-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2001.0581"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63165-8_172"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00096-6"},{"key":"e_1_2_1_7_1","volume-title":"Campagnolo","author":"Bournez Olivier","year":"2008","unstructured":"Olivier Bournez and Manuel L . Campagnolo . 2008 . New Computational Paradigms. Changing Conceptions of What is Computable. Springer-Verlag , New York, 383--423. Olivier Bournez and Manuel L. Campagnolo. 2008. New Computational Paradigms. Changing Conceptions of What is Computable. Springer-Verlag, New York, 383--423."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11750321_60"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.12.005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exh036"},{"key":"e_1_2_1_12_1","volume-title":"On the functions generated by the general purpose analog computer. CoRR abs\/1602.00546","author":"Bournez Olivier","year":"2016","unstructured":"Olivier Bournez , Daniel S. Gra\u00e7a , and Amaury Pouly . 2016. On the functions generated by the general purpose analog computer. CoRR abs\/1602.00546 ( 2016 ). Retrieved from http:\/\/arxiv.org\/abs\/1602.00546. Olivier Bournez, Daniel S. Gra\u00e7a, and Amaury Pouly. 2016. On the functions generated by the general purpose analog computer. CoRR abs\/1602.00546 (2016). Retrieved from http:\/\/arxiv.org\/abs\/1602.00546."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2016.05.002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0016-0032(31)90616-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019686124563"},{"key":"e_1_2_1_16_1","volume-title":"Unconventional Models of Computations","author":"Copeland B. Jack","unstructured":"B. Jack Copeland . 1998. Even Turing machines can compute uncomputable functions . In Unconventional Models of Computations , C.S. Calude, J. Casti, and M.J. Dinneen (Eds.). Springer-Verlag . B. Jack Copeland. 1998. Even Turing machines can compute uncomputable functions. In Unconventional Models of Computations, C.S. Calude, J. Casti, and M.J. Dinneen (Eds.). Springer-Verlag."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015607401307"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/52.4.671"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1093\/imamci\/8.2.135"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200210)48:1+%3C45::AID-MALQ45%3E3.0.CO;2-7"},{"key":"e_1_2_1_22_1","first-page":"4","article-title":"Some recent developments on Shannon\u2019s general purpose analog computer","volume":"50","author":"Gra\u00e7a Daniel S.","year":"2004","unstructured":"Daniel S. Gra\u00e7a . 2004 . Some recent developments on Shannon\u2019s general purpose analog computer . Math. Log. Quart. 50 , 4 -- 5 (2004), 473--485. Daniel S. Gra\u00e7a. 2004. Some recent developments on Shannon\u2019s general purpose analog computer. Math. Log. Quart. 50, 4--5 (2004), 473--485.","journal-title":"Math. Log. Quart."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 4th International Conference on Computability and Complexity in Analysis (CCA\u201907)","volume":"202","author":"Gra\u00e7a Daniel S.","unstructured":"Daniel S. Gra\u00e7a , Jorge Buescu , and Manuel L. Campagnolo . 2007. Boundedness of the domain of definition is undecidable for polynomial ODEs . In Proceedings of the 4th International Conference on Computability and Complexity in Analysis (CCA\u201907) (Electron. Notes Theor. Comput. Sci.), R. Dillhage, T. Grubba, A. Sorbi, K. Weihrauch, and N. Zhong (Eds.) , Vol. 202 . Elsevier, 49--57. Daniel S. Gra\u00e7a, Jorge Buescu, and Manuel L. Campagnolo. 2007. Boundedness of the domain of definition is undecidable for polynomial ODEs. In Proceedings of the 4th International Conference on Computability and Complexity in Analysis (CCA\u201907) (Electron. Notes Theor. Comput. Sci.), R. Dillhage, T. Grubba, A. Sorbi, K. Weihrauch, and N. Zhong (Eds.), Vol. 202. Elsevier, 49--57."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2009.04.055"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0885-064X(03)00034-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225151"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0286-0"},{"key":"e_1_2_1_29_1","volume-title":"Complexity Theory of Real Functions. Birkha\u00fcser","author":"I Ko.","unstructured":"Ker- I Ko. 1991. Complexity Theory of Real Functions. Birkha\u00fcser , Boston . Ker-I Ko. 1991. Complexity Theory of Real Functions. Birkha\u00fcser, Boston."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54509-3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30440-3_19"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00248-0"},{"key":"e_1_2_1_33_1","first-page":"283","article-title":"Solving initial value problems in polynomial time. In Proceedings of the 22 (JAIIO-PANEL\u201993)","volume":"2","author":"M\u00fcller Norbert","year":"1993","unstructured":"Norbert M\u00fcller and Bernd Moiske . 1993 . Solving initial value problems in polynomial time. In Proceedings of the 22 (JAIIO-PANEL\u201993) , Part 2. 283 -- 293 . Norbert M\u00fcller and Bernd Moiske. 1993. Solving initial value problems in polynomial time. In Proceedings of the 22 (JAIIO-PANEL\u201993), Part 2. 283--293.","journal-title":"Part"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1138772.1716404"},{"key":"e_1_2_1_35_1","volume-title":"Computational complexity of solving polynomial differential equations over unbounded domains with non-rational coefficients. CoRR abs\/1608.00135","author":"Pouly Amaury","year":"2016","unstructured":"Amaury Pouly . 2016. Computational complexity of solving polynomial differential equations over unbounded domains with non-rational coefficients. CoRR abs\/1608.00135 ( 2016 ). Retrieved from http:\/\/arxiv.org\/abs\/1608.00135. Amaury Pouly. 2016. Computational complexity of solving polynomial differential equations over unbounded domains with non-rational coefficients. CoRR abs\/1608.00135 (2016). Retrieved from http:\/\/arxiv.org\/abs\/1608.00135."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.02.002"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1974-0347575-8"},{"key":"e_1_2_1_38_1","first-page":"101","article-title":"Undecidability of event detection for ODEs","volume":"29","author":"Ruohonen Keijo","year":"1993","unstructured":"Keijo Ruohonen . 1993 . Undecidability of event detection for ODEs . J. Info. Process. Cybernet. 29 (1993), 101 -- 113 . Keijo Ruohonen. 1993. Undecidability of event detection for ODEs. J. Info. Process. Cybernet. 29 (1993), 101--113.","journal-title":"J. Info. Process. Cybernet."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58131-6_59"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1941201337"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1524\/9783486755183"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3127496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3127496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:29Z","timestamp":1750217429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3127496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,4]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3127496"],"URL":"https:\/\/doi.org\/10.1145\/3127496","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,4]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}