# The complexity of N-body simulation

Published

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