Average-Case Polynomial-Time Computability of Hamiltonian Dynamics

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 28
  • Download : 0
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.
Publisher
Schloss Dagstuhl – Leibniz Center for Informatics
Issue Date
2018-08-31
Language
English
Citation

43rd International Symposium on Mathematical Foundations of Computer Science

ISSN
1868-8969
DOI
10.4230/LIPIcs.MFCS.2018.30
URI
http://hdl.handle.net/10203/249438
Appears in Collection
CS-Conference Papers(학술회의논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0