Average-case polynomial-time computability of hamiltonian dynamics

Akitoshi Kawamura, Holger Thies, Martin Ziegler

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

9 被引用数 (Scopus)

抄録

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.

本文言語英語
ホスト出版物のタイトル43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
編集者Igor Potapov, James Worrell, Paul Spirakis
出版社Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN(印刷版)9783959770866
DOI
出版ステータス出版済み - 8月 1 2018
イベント43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, 英国
継続期間: 8月 27 20188月 31 2018

出版物シリーズ

名前Leibniz International Proceedings in Informatics, LIPIcs
117
ISSN(印刷版)1868-8969

その他

その他43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
国/地域英国
CityLiverpool
Period8/27/188/31/18

!!!All Science Journal Classification (ASJC) codes

  • ソフトウェア

フィンガープリント

「Average-case polynomial-time computability of hamiltonian dynamics」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル