Document Open Access Logo

Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations

Authors Olivier Bournez , Arnaud Durand

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.23.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Olivier Bournez
  • Laboratoire d'Informatique de l'X (LIX), CNRS, Ecole Polytechnique, Institut Polytechnique de Paris, 91128 Palaiseau Cedex, France
Arnaud Durand
  • Université Paris Diderot, IMJ-PRG, CNRS UMR 7586, Case 7012, 75205 Paris cedex 13, France

Funding

  • Bournez, Olivier: Supported by RACAF Project from Agence National de la Recherche and Labex Digicosme Project ACDC.

Acknowledgements

We would like to thank Sabrina Ouazzani for many scientific discussions about the results in this article.

Cite AsGet BibTex

Olivier Bournez and Arnaud Durand. Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.23

Abstract

This paper studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs). It presents a new framework using discrete ODEs as a central tool for computation and algorithm design. We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes. The proposed framework presents an original point of view on complexity and computation classes. It unifies several constructions that have been proposed for characterizing these classes including classical approaches in implicit complexity using restricted recursion schemes, as well as recent characterizations of computability and complexity by classes of continuous ordinary differential equations. It also helps understanding the relationships between analog computations and classical discrete models of computation theory. At a more technical point of view, this paper points out the fundamental role of linear (discrete) ordinary differential equations and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming many algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Models of computation
  • Theory of computation → Computability
  • Theory of computation → Recursive functions
  • Computer systems organization → Analog computers
  • Theory of computation → Complexity classes
  • Theory of computation → Complexity theory and logic
  • Mathematics of computing → Differential equations
  • Mathematics of computing → Ordinary differential equations
  • Mathematics of computing → Differential calculus
Keywords
  • Implicit complexity
  • discrete ordinary differential equations
  • recursion scheme

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. V. I. Arnold. Ordinary Differential Equations. MIT Press, 1978. Google Scholar
  2. S. Bellantoni and S. Cook. A new recursion-theoretic characterization of the poly-time functions. Computational Complexity, 2:97-110, 1992. Google Scholar
  3. G. Birkhoff and G.-C. Rota. Ordinary Differential Equations. John Wiley & Sons, 4th edition, 1989. Google Scholar
  4. 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 ACM, 64(6):38:1-38:76, 2017. URL: https://doi.org/10.1145/3127496.
  5. Olivier Bournez and Amaury Pouly. A Survey on Analog Models of Computation. In Vasco Brattka and Peter Hertling, editors, Handbook of Computability and Complexity in Analysis. Springer. To appear, 2018. Google Scholar
  6. Manuel L. Campagnolo. Computational Complexity of Real Valued Recursive Functions and Analog Circuits. PhD thesis, Universidade Técnica de Lisboa, 2001. Google Scholar
  7. Manuel L. Campagnolo, Cristopher Moore, and José Félix Costa. An analog characterization of the Grzegorczyk hierarchy. Journal of Complexity, 18(4):977-1000, 2002. Google Scholar
  8. A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, pages 24-30. North-Holland, Amsterdam, 1962. Google Scholar
  9. E. A. Coddington and N. Levinson. Theory of Ordinary Differential Equations. Mc-Graw-Hill, 1955. Google Scholar
  10. Pieter Collins and Daniel S Graça. Effective computability of solutions of ordinary differential equations the thousand monkeys approach. Electronic Notes in Theoretical Computer Science, 221:103-114, 2008. Google Scholar
  11. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms (third edition). MIT press, 2009. Google Scholar
  12. AO Gelfand. Calcul des différences finies. Dunod, 1963. Google Scholar
  13. David Gleich. Finite calculus: A tutorial for solving nasty sums. Stanford University, 2005. Google Scholar
  14. Ronald L Graham, Donald E Knuth, Oren Patashnik, and Stanley Liu. Concrete mathematics: a foundation for computer science. Computers in Physics, 3(5):106-107, 1989. Google Scholar
  15. FA Izadi, N Aliev, and G Bagirov. Discrete Calculus by Analogy. Bentham Science Publishers, 2009. Google Scholar
  16. Charles Jordan and Károly Jordán. Calculus of finite differences, volume 33. American Mathematical Soc., 1965. Google Scholar
  17. L. Kalmár. Egyzzerü példa eldönthetetlen aritmetikai problémára. Mate és Fizikai Lapok, 50:1-23, 1943. Google Scholar
  18. A. Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 149-160. IEEE, 2009. Google Scholar
  19. Ker-I Ko. On the Computational Complexity of Ordinary Differential Equations. Information and Control, 58(1-3):157-194, 1983. Google Scholar
  20. Gustavo Lau. Discrete calculus. URL: http://www.acm.ciens.ucv.ve/main/entrenamiento/material/DiscreteCalculus.pdf.
  21. D. Leivant. Predicative recurrence and computational complexity I: Word recurrence and poly-time. In Peter Clote and Jeffery Remmel, editors, Feasible Mathematics II, pages 320-343. Birkhäuser, 1994. Google Scholar
  22. D. Leivant and J-Y Marion. Lambda Calculus Characterizations of Poly-Time. Fundamenta Informatica, 19(1,2):167,184, September 1993. Google Scholar
  23. Daniel Leivant and Jean-Yves Marion. Ramified recurrence and computational complexity II: substitution and poly-space. In L. Pacholski and J. Tiuryn, editors, Computer Science Logic, 8th Workshop, CSL'94, volume 933 of Lecture Notes in Computer Science, pages 369-380, Kazimierz, Poland, 1995. Springer. Google Scholar
  24. Bruno Loff, José Félix Costa, and Jerzy Mycka. The New Promise of Analog Computation. In Computability in Europe 2007: Computation and Logic in the Real World., 2007. Google Scholar
  25. Cristopher Moore. Recursion theory on the reals and continuous-time computation. Theoretical Computer Science, 162(1):23-44, August 1996. Google Scholar
  26. Jerzy Mycka and José Félix Costa. What lies beyond the mountains? Computational systems beyond the Turing limit. European Association for Theoretical Computer Science Bulletin, 85:181-189, February 2005. Google Scholar
  27. Jerzy Mycka and José Félix Costa. The P ̸ = NP conjecture in the context of real and complex analysis. Journal of Complexity, 22(2):287-303, 2006. Google Scholar
  28. P. Odifreddi. Classical Recursion Theory, volume 125 of Studies in Logic and the foundations of mathematics. North-Holland, April 1992. Google Scholar
  29. Amaury Pouly. Continuous models of computation: from computability to complexity. PhD thesis, Ecole Polytechnique and Unidersidade Do Algarve, 2015. https://pastel.archives-ouvertes.fr/tel-01223284, Ackermann Award 2017. Google Scholar
  30. H. E. Rose. Subrecursion, Functions and Hierarchies. Clarendon Press, Oxford, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact