The complexity of N-body simulation


Conference Paper

© Springer-Verlag Berlin Heidelberg 1993. The n-body simulation problem is stated as follows: Given initial positions and velocities of n particles that have pair-wise force interactions, simulate the movement of these particles so as to determine the positions of the particles at a future time. In this paper, we give the first known n-body simulation algorithms with rigorous proofs of bounded error. The reachability problem is to determine if a specific particle will reach a certain region at some specified target time. In the case we require poly(n) bits of accuracy and where the target time is poly(n), our complexity bounds are surprisingly PSPACE. We also have matching lower bounds for n-body simulation problem (in comparison all previous lower bound proofs required either artificial external forces or obstacles). We show that the reachability problem for a set of interacting particles in three dimensions is PSPACE-hard.

Duke Authors

Cited Authors

  • Reif, JH; Tate, SR

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 700 LNCS /

Start / End Page

  • 162 - 176

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540569398

Citation Source

  • Scopus