Uncontrollable computational growth in theoretical physics (Q1071512)

Some new results in the theory of synchronous parallel computation indicate there may be fundamentally unavoidable limitations to computing in certain kinds of large computational problems arising naturally in science and engineering. These limitations are in the nature of uncontrolled growth (discontinuous jumps) in computation times under fixed programming schemes, and arise for computations allowing arbitrary (uniform) inputs over \(F^ n\) for sufficiently large n, where F is a finite field. Instances of such discontinuity may appear, for example, in very-large-scale Monte Carlo simulations, such as those being contemplated for carrying out quantum chromodynamics (QCD) computations on lattices of substantially larger size than is now practicable. In this case, the QCD simulation may encounter abnormally (and unexplained) long run times on particular internally generated updates, resulting in distortion among time-weighted runs. The mechanism of these updates is believed to satisfy our necessary assumption for fixed encodings over uniform inputs.