License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.30
URN: urn:nbn:de:0030-drops-96125
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9612/
Go to the corresponding LIPIcs Volume Portal

Kawamura, Akitoshi ; Thies, Holger ; Ziegler, Martin

Average-Case Polynomial-Time Computability of Hamiltonian Dynamics

pdf-format:
LIPIcs-MFCS-2018-30.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{kawamura_et_al:LIPIcs:2018:9612,
  author =	{Akitoshi Kawamura and Holger Thies and Martin Ziegler},
  title =	{{Average-Case Polynomial-Time Computability of Hamiltonian Dynamics}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9612},
  URN =		{urn:nbn:de:0030-drops-96125},
  doi =		{10.4230/LIPIcs.MFCS.2018.30},
  annote =	{Keywords: Computable Analysis, Real computation, Dynamical systems, Average-case complexity, Computation in physics}
}

Keywords: Computable Analysis, Real computation, Dynamical systems, Average-case complexity, Computation in physics
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI