In this paper we show that several classes of languages from computational complexity theory, such as , can be characterized in a continuous manner by using only polynomial differential equations. This characterization applies not only to languages, but also to classes of functions, such as the classes defining the Grzegorczyk hierarchy, which implies an analog characterization of the class of elementary computable functions and the class of primitive recursive functions.
O.Bournez, M.L.Campagnolo, D.S.Graça and E.Hainry, The general purpose analog computer and computable analysis are two equivalent paradigms of analog computation, in: Proc. Theory and Applications of Models of Computation (TAMC 06), J.-Y.Cai, S.B.Cooper and A.Li, eds, Lecture Notes in Computer Science, Vol. 3959, Springer, 2006, pp. 631–643. doi:10.1007/11750321_60.
2.
O.Bournez, M.L.Campagnolo, D.S.Graça and E.Hainry, Polynomial differential equations compute all real computable functions on computable compact intervals, Journal of Complexity23(3) (2007), 317–335. doi:10.1016/j.jco.2006.12.005.
3.
O.Bournez, D.S.Graça and A.Pouly, Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length – the general purpose analog computer and computable analysis are two efficiently equivalent models of computations, in: Proc. 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), I.Chatzigiannakis, M.Mitzenmacher, Y.Rabani and D.Sangiorgi, eds, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 55, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016, pp. 109:1–109:15.
4.
O.Bournez, D.S.Graça and A.Pouly, Computing with polynomial ordinary differential equations, Journal of Complexity36 (2016), 106–140. doi:10.1016/j.jco.2016.05.002.
5.
O.Bournez, D.S.Graça and A.Pouly, Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length, Journal of the ACM64(6) (2017), 38:1–38:76. doi:10.1145/3127496.
6.
O.Bournez, D.S.Graça and A.Pouly, On the functions generated by the general purpose analog computer, Information and Computation257 (2017), 34–57. doi:10.1016/j.ic.2017.09.015.
7.
O.Bournez and E.Hainry, An analog characterization of elementarily computable functions over the real numbers, in: Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Lecture Notes in Computer Science, Vol. 3142, Springer, 2004, pp. 269–280. doi:10.1007/978-3-540-27836-8_25.
8.
O.Bournez and E.Hainry, Elementarily computable functions over the real numbers and -sub-recursive functions, Theoretical Computer Science348(2–3) (2005), 130–147. doi:10.1016/j.tcs.2005.09.010.
9.
M.S.Branicky, Universal computation and other capabilities of hybrid and continuous dynamical systems, Theoretical Computer Science138(1) (1995), 67–100. doi:10.1016/0304-3975(94)00147-B.
10.
V.Brattka, P.Hertling and K.Weihrauch, A tutorial on computable analysis, in: New Computational Paradigms: Changing Conceptions of What Is Computable, S.B.Cooper, B.Löwe and A.Sorbi, eds, Springer, 2008, pp. 425–491. doi:10.1007/978-0-387-68546-5_18.
11.
V.Bush, The differential analyzer. A new machine for solving differential equations, Journal of the Franklin Institute212 (1931), 447–488. doi:10.1016/S0016-0032(31)90616-9.
12.
M.Campagnolo and C.Moore, Upper and lower bounds on continuous-time computation, in: Proc. 2nd International Conference on Unconventional Models of Computation – UMC’2K, I.Antoniou, C.Calude and M.Dinneen, eds, Springer, 2001, pp. 135–153. doi:10.1007/978-1-4471-0313-4_12.
13.
M.L.Campagnolo, C.Moore and J.F.Costa, Iteration, inequalities, and differentiability in analog computers, Journal of Complexity16(4) (2000), 642–660. doi:10.1006/jcom.2000.0559.
14.
M.L.Campagnolo, C.Moore and J.F.Costa, An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity18(4) (2002), 977–1000. doi:10.1006/jcom.2002.0655.
15.
O.Goldreich, Computational Complexity: A Conceptual Perspective, Revised 1st edn, Cambridge University Press, 2008.
16.
D.S.Graça, Some recent developments on Shannon’s general purpose analog computer, Mathematical Logic Quarterly50(4–5) (2004), 473–485. doi:10.1002/malq.200310113.
17.
D.S.Graça, M.L.Campagnolo and J.Buescu, Computability with polynomial differential equations, Advances in Applied Mathematics40(3) (2008), 330–349. doi:10.1016/j.aam.2007.02.003.
18.
D.S.Graça and J.F.Costa, Analog computers and recursive functions over the reals, Journal of Complexity19(5) (2003), 644–664. doi:10.1016/S0885-064X(03)00034-7.
19.
A.Grzegorczyk, Some classes of recursive functions, Rozprawy matematyczne4 (1953), 1–45.
20.
J.H.Hubbard and B.H.West, Differential Equations: A Dynamical Systems Approach – Higher-Dimensional Systems, Springer, 1995.
21.
K.-I.Ko and H.Friedman, Computational complexity of real functions, Theoretical Computer Science20 (1982), 323–352. doi:10.1016/S0304-3975(82)80003-0.
