Skip to main content

The complexity of N-body simulation

Publication ,  Conference
Reif, JH; Tate, SR
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 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 Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 1993

Volume

700 LNCS

Start / End Page

162 / 176

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Tate, S. R. (1993). The complexity of N-body simulation. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 700 LNCS, pp. 162–176). https://doi.org/10.1007/3-540-56939-1_70

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 1993

Volume

700 LNCS

Start / End Page

162 / 176

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences