The complexity of N-body simulation
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 Scholars
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences