Document Open Access Logo

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

Authors Olivier Bournez, Daniel S. Graça, Amaury Pouly

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.109.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Olivier Bournez
Daniel S. Graça
Amaury Pouly

Cite As Get BibTex

Olivier Bournez, Daniel S. Graça, and Amaury 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 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 109:1-109:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.109

Abstract

The outcomes of this paper 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 differential equations with polynomial right-hand side. 

This result gives a purely continuous (time and space) elegant and simple characterization of P. We believe it is the first time such 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. 

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.

Continuous-Time Models of Computation. Our results can also be interpreted in terms of analog computers or analog model 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 at the computability and complexity level, 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 at a computability and at a computational complexity level.

Subject Classification

Keywords
  • Analog Models of Computation
  • Continuous-Time Models of Computation
  • Computable Analysis
  • Implicit Complexity
  • Computational Complexity
  • Ordinary Diff

Metrics

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

References

  1. Rajeev Alur and David L. Dill. Automata for modeling real-time systems. In Mike Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 322-335. Springer, 1990. Google Scholar
  2. A. Ben-Hur, H. T. Siegelmann, and S. Fishman. A theory of complexity for continuous time systems. J. Complexity, 18(1):51-86, 2002. Google Scholar
  3. Asa Ben-Hur, Joshua Feinberg, Shmuel Fishman, and Hava T. Siegelmann. Probabilistic analysis of a differential equation for linear programming. Journal of Complexity, 19(4):474-510, 2003. URL: http://dx.doi.org/S0885-064X(03)00032-3.
  4. L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer, 1998. Google Scholar
  5. 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 J.-Y. Cai, S. B. Cooper, and A. Li, editors, Theory and Applications of Models of Computation TAMC'06, LNCS 3959, pages 631-643. Springer-Verlag, 2006. Google Scholar
  6. O. Bournez, M. L. Campagnolo, D. S. Graça, and E. Hainry. Polynomial differential equations compute all real computable functions on computable compact intervals. J. Complexity, 23(3):317-335, 2007. Google Scholar
  7. Olivier Bournez. Some bounds on the computational power of piecewise constant derivative systems (extended abstract). In ICALP, pages 143-153, 1997. URL: http://dx.doi.org/10.1007/3-540-63165-8_172.
  8. Olivier Bournez. Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy. Theoret. Comput. Sci., 210(1):21-71, 1999. Google Scholar
  9. Olivier Bournez and Manuel L. Campagnolo. A survey on continuous time computations. In S.B. Cooper, B. Löwe, and A. Sorbi, editors, New Computational Paradigms. Changing Conceptions of What is Computable, pages 383-423. Springer-Verlag, New York, 2008. Google Scholar
  10. Olivier Bournez, Felipe Cucker, Paulin Jacobé de Naurois, and Jean-Yves Marion. Implicit complexity over an arbitrary structure: Sequential and parallel polynomial time. Journal of Logic and Computation, 15(1):41-58, 2005. Google Scholar
  11. V. Bush. The differential analyzer. A new machine for solving differential equations. J. Franklin Inst., 212:447-488, 1931. Google Scholar
  12. C. S. Calude and B. Pavlov. Coins, quantum measurements, and Turing’s barrier. Quantum Information Processing, 1(1-2):107-127, April 2002. Google Scholar
  13. B. Jack Copeland. Even Turing machines can compute uncomputable functions. In C.S. Calude, J. Casti, and M.J. Dinneen, editors, Unconventional Models of Computations. Springer-Verlag, 1998. Google Scholar
  14. B. Jack Copeland. Accelerating Turing machines. Minds and Machines, 12:281-301, 2002. Google Scholar
  15. E. B. Davies. Building infinite machines. The British Journal for the Philosophy of Science, 52:671-682, 2001. Google Scholar
  16. Leonid Faybusovich. Dynamical systems which solve optimization problems with linear constraints. IMA Journal of Mathematical Control and Information, 8:135-149, 1991. Google Scholar
  17. R. P. Feynman. Simulating physics with computers. Internat. J. Theoret. Phys., 21(6/7):467-488, 1982. Google Scholar
  18. Marco Gori and Klaus Meer. A step towards a complexity theory for analog systems. Mathematical Logic Quarterly, 48(Suppl. 1):45-58, 2002. Google Scholar
  19. D. S. Graça. Some recent developments on Shannon’s General Purpose Analog Computer. Math. Log. Quart., 50(4-5):473-485, 2004. Google Scholar
  20. D. S. Graça, J. Buescu, and M. L. Campagnolo. Boundedness of the domain of definition is undecidable for polynomial ODEs. In R. Dillhage, T. Grubba, A. Sorbi, K. Weihrauch, and N. Zhong, editors, 4th International Conference on Computability and Complexity in Analysis (CCA 2007), volume 202 of Electron. Notes Theor. Comput. Sci., pages 49-57. Elsevier, 2007. Google Scholar
  21. D. S. Graça, J. Buescu, and M. L. Campagnolo. Computational bounds on polynomial differential equations. Appl. Math. Comput., 215(4):1375-1385, 2009. Google Scholar
  22. D. S. Graça, M. L. Campagnolo, and J. Buescu. Computability with polynomial differential equations. Adv. Appl. Math., 40(3):330-349, 2008. Google Scholar
  23. Daniel S. Graça and José Félix Costa. Analog computers and recursive functions over the reals. Journal of Complexity, 19(5):644-664, 2003. Google Scholar
  24. Erich Grädel and Klaus Meer. Descriptive complexity theory over the real numbers. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 315-324, Las Vegas, Nevada, 29May-1June 1995. ACM Press. Google Scholar
  25. Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302-311. ACM, 1984. Google Scholar
  26. A. Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. Computational Complexity, 19(2):305-332, 2010. Google Scholar
  27. Ker-I Ko. Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhaüser, Boston, 1991. Google Scholar
  28. Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, and Akiko Yoshise. A unified approach to interior point algorithms for linear complementarity problems, volume 538. Springer Science &Business Media, 1991. Google Scholar
  29. Bruce J MacLennan. Analog computation. In Encyclopedia of complexity and systems science, pages 271-294. Springer, 2009. Google Scholar
  30. Cristopher Moore. Recursion theory on the reals and continuous-time computation. Theoretical Computer Science, 162(1):23-44, 5 August 1996. Google Scholar
  31. N. Müller and B. Moiske. Solving initial value problems in polynomial time. In Proc. 22 JAIIO - PANEL 1993, Part 2, pages 283-293, 1993. Google Scholar
  32. J. Mycka and J. F. Costa. The p≠ np conjecture in the context of real and complex analysis. J. Complexity, 22(2):287-303, 2006. Google Scholar
  33. Amaury Pouly. Continuous models of computation: from computability to complexity. PhD thesis, Ecole Polytechnique and Unidersidade Do Algarve, Defended on July 6, 2015. 2015. https://pastel.archives-ouvertes.fr/tel-01223284. Google Scholar
  34. Amaury Pouly and Daniel S. Graça. Computational complexity of solving polynomial differential equations over unbounded domains. Theor. Comput. Sci., 626:67-82, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.02.002.
  35. M. B. Pour-El. Abstract computability and its relations to the general purpose analog computer. Trans. Amer. Math. Soc., 199:1-28, 1974. Google Scholar
  36. Keijo Ruohonen. Undecidability of event detection for ODEs. Journal of Information Processing and Cybernetics, 29:101-113, 1993. Google Scholar
  37. Keijo Ruohonen. Event detection for ODEs and nonrecursive hierarchies. In Proceedings of the Colloquium in Honor of Arto Salomaa. Results and Trends in Theoretical Computer Science (Graz, Austria, June 10-11, 1994), volume 812 of Lecture Notes in Computer Science, pages 358-371. Springer-Verlag, Berlin, 1994. Google Scholar
  38. C. E. Shannon. Mathematical theory of the differential analyser. Journal of Mathematics and Physics MIT, 20:337-354, 1941. Google Scholar
  39. Bernd Ulmann. Analog computing. Walter de Gruyter, 2013. Google Scholar
  40. K. Weihrauch. Computable Analysis: an Introduction. Springer, 2000. 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 About DROPS Imprint Privacy Contact