Document Open Access Logo

Average-Case Polynomial-Time Computability of Hamiltonian Dynamics

Authors Akitoshi Kawamura, Holger Thies, Martin Ziegler

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.30.pdf
  • Filesize: 487 kB
  • 17 pages

Document Identifiers

Author Details

Akitoshi Kawamura
  • Kyushu University, Fukuoka, Japan
Holger Thies
  • University of Tokyo, Tokyo, Japan
Martin Ziegler
  • KAIST, Daejeon, Republic of Korea

Cite As Get BibTex

Akitoshi Kawamura, Holger Thies, and Martin Ziegler. Average-Case Polynomial-Time Computability of Hamiltonian Dynamics. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.30

Abstract

We apply average-case complexity theory to physical problems modeled by continuous-time dynamical systems. The computational complexity when simulating such systems for a bounded time-frame mainly stems from trajectories coming close to complex singularities of the system. We show that if for most initial values the trajectories do not come close to singularities the simulation can be done in polynomial time on average. For Hamiltonian systems we relate this to the volume of "almost singularities" in phase space and give some general criteria to show that a Hamiltonian system can be simulated efficiently on average. As an application we show that the planar circular-restricted three-body problem is average-case polynomial-time computable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Computable Analysis
  • Real computation
  • Dynamical systems
  • Average-case complexity
  • Computation in physics

Metrics

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

References

  1. Olivier Bournez, Daniel S. Graça, and Amaury Pouly. On the complexity of solving initial value problems. In ISSAC 2012-Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, pages 115-121. ACM, New York, 2012. URL: http://dx.doi.org/10.1145/2442829.2442849.
  2. Daniel S Graça, Ning Zhong, and Jorge Buescu. Computability, noncomputability and undecidability of maximal intervals of IVPs. Transactions of the American Mathematical Society, 361(6):2913-2927, 2009. Google Scholar
  3. A. Grzegorczyk. On the definitions of computable real continuous functions. Fund. Math., 44:61-71, 1957. Google Scholar
  4. Akitoshi Kawamura. Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. Computational Complexity, 19(2):305-332, 2010. Google Scholar
  5. Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. ACM Transactions on Computation Theory, 4(2):Article 5, 2012. Google Scholar
  6. Ker-I Ko. On the computational complexity of ordinary differential equations. Information and Control, 58(1-3):157-194, 1983. Google Scholar
  7. Ker-I Ko. Complexity theory of real functions. Progress in Theoretical Computer Science. Birkhäuser Boston Inc., Boston, MA, 1991. URL: http://dx.doi.org/10.1007/978-1-4684-6802-1.
  8. Ker-I Ko and Harvey Friedman. Computational complexity of real functions. Theoretical Computer Science, 20(3):323-352, 1982. URL: http://dx.doi.org/10.1016/S0304-3975(82)80003-0.
  9. Ker-I Ko and Harvey Friedman. Computing power series in polynomial time. Advances in Applied Mathematics, 9(1):40-50, 1988. Google Scholar
  10. Hikosaburo Komatsu. A characterization of real analytic functions. Proceedings of the Japan Academy, 36(3):90-93, 1960. Google Scholar
  11. Wang Sang Koon, Martin W. Lo, Jerrold E. Marsden, and Shane D. Ross. Dynamical systems, the three-body problem and space mission design. World Scientific, 2000. Google Scholar
  12. Daniel Lacombe. Sur les possibilités d'extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. In Le raisonnement en mathématiques et en sciences expérimentales, Colloques Internationaux du Centre National de la Recherche Scientifique, LXX, pages 67-75. Editions du Centre National de la Recherche Scientifique, Paris, 1958. Google Scholar
  13. Leonid A. Levin. Average case complete problems. SIAM Journal on Computing, 15(1):285-286, 1986. Google Scholar
  14. X. Mao. Stochastic Differential Equations and Their Applications. Ellis Horwood series in mathematics and its applications. Horwood Pub., 1997. Google Scholar
  15. Andrea Milani. Chaos in the three body problem. In Predictability, stability, and chaos in N-body dynamical systems, pages 11-33. Springer, 1991. Google Scholar
  16. R. H. Miller. Numerical difficulties with the gravitational n-body problem. In Dale G. Bettis, editor, Proceedings of the Conference on the Numerical Solution of Ordinary Differential Equations, pages 260-275, Berlin, Heidelberg, 1974. Springer Berlin Heidelberg. Google Scholar
  17. Bernd Moiske and Norbert Th. Müller. Solving initial value problems in polynomial time. In Proc. 22 JAIIO - PANEL ’93, Part 2, pages 283-293, Buenos Aires, 1993. URL: http://www.uni-trier.de/~mueller.
  18. Norbert Th. Müller. Uniform Computational Complexity of Taylor Series. In Proc. 14th International Colloquium on Automata, Languages, and Programming, volume 267 of LNCS, pages 435-444. Springer, 1987. Google Scholar
  19. Norbert Th. Müller. Polynomial time computation of Taylor series. Proc. 22 JAIIO-PANEL’93, Part 2, Buenos Aires, 259:281, 1993. Google Scholar
  20. Norbert Th. Müller. Constructive Aspects of Analytic Functions. In Proc. Workshop on Computability and Complexity in Analysis, volume 190 of InformatikBerichte, pages 105-114. FernUniversität Hagen, 1995. Google Scholar
  21. Donald G. Saari. Improbability of Collisions in Newtonian Gravitational Systems. II. Transactions of the American Mathematical Society, 181:351-368, 1973. URL: http://dx.doi.org/10.2307/1996638.
  22. Donald G. Saari. A global existence theorem for the four-body problem of Newtonian mechanics. Journal of Differential Equations, 26(1):80-111, 1977. URL: http://dx.doi.org/10.1016/0022-0396(77)90100-0.
  23. Matthias Schröder, Florian Steinberg, and Martin Ziegler. Average-Case Bit-Complexity Theory of Real Functions. In Mathematical Aspects of Computer and Information Sciences, pages 505-519. Springer, Cham, 2015. URL: http://dx.doi.org/10.1007/978-3-319-32859-1_43.
  24. A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(1):230-265, 1936. URL: http://dx.doi.org/10.1112/plms/s2-42.1.230.
  25. Klaus Weihrauch. Computable Analysis. Springer, Berlin/Heidelberg, 2000. Google Scholar
  26. Andrew Chi-Chih Yao. Classical physics and the Church-Turing Thesis. Journal of the ACM (JACM), 50(1):100-105, 2003. Google Scholar
  27. Lei Zhao. Quasi-Periodic Almost-Collision Orbits in the Spatial Three-Body Problem. Communications on Pure and Applied Mathematics, 68(12):2144-2176, 2015. 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