Publications [#329002] of John H. Reif

Conference articles PUBLISHED

1. Reif, JH; Tate, SR, The complexity of N-body simulation, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 700 LNCS (January, 1993), pp. 162-176, ISBN 9783540569398 [doi]
   (last updated on 2026/01/14)

   Abstract:
   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.