What is the "curse of dimensionality" in molecular dynamics? The 'curse of dimensionality' or the 'bottleneck problem' in molecular dynamics is explained in page 5 and 6 of Ab Initio Molecular Dynamics: Basic Theory and Advanced Methods by Dominic Marx and Jurg Hutter .

They proved that Car-Parrinello MD outperforms classical MD with a computational advantage growing as $\sim 10^N$ with system size, which I am unable to understand, especially the last paragraph of page 5.

To be more specific, I am copying the relevant contents:


  In the case of using classical mechanics to describe the dynamics - which is the focus of the present book - the limiting step for large systems is the first one, why should this be so? There are $3N-6$ internal degrees of freedom that span the global potential energy surface of an unconstrained $N$-body system.  Using, for simplicity, 10 discretization points per coordinate implies that of the order of $10^{3N-6}$ electronic structure calculations are needed in order to map such a global potential energy surface. Thus, the computational workload for the first step in the approach outlined above grows roughly like ∼$10^N$ with increasing system size ∼$N$. This is what might be called the curse of dimensionality or dimensionality bottleneck of calculations that rely on global
  potential energy surfaces.


What is needed in ab initio molecular dynamics instead? I am confused about the parts placed in bold:


  Suppose that a useful trajectory consists of about $10^M$ molecular dynamics steps, i.e. $10^M$ electronic structure calculations are needed to generate one trajectory. Furthermore, it is assumed that $10^n$ independent trajectories are necessary in order to average over different initial conditions so that $10^{M+n}$ ab initio molecular dynamics steps are required in total. Finally, it is assumed that each single-point electronic structure calculation needed to devise the global potential energy surface and one ab initio molecular dynamics time step require roughly the same amount of cpu time. Based on this truly simplistic order of magnitude estimate, the advantage of ab initio molecular dynamics vs.  calculations relying on the computation of a global potential energy surface amounts to about $10^{3N-6-M-n}$. The crucial point is that for a given statistical accuracy (that is for $M$ and $n$ fixed and independent of $N$) and for a given electronic structure method, the computational advantage of ``on-the-fly” approaches grows like ∼$10^N$ with system size. Thus, Car–Parrinello methods always outperform the traditional three-step approaches if the system is sufficiently large and complex. Conversely, computing global potential energy surfaces beforehand and running many classical trajectories afterwards without much additional cost always pays off for a given system size $N$ like ∼$10^{M+n}$ if the system is small enough so that a global potential energy surface can be computed and parameterized.


How do the bolded points prove that fact that "computational advantage of 'on-the-fly' approaches grows like ∼$10^N$ with system size" over classical MD?
It's certainly more of a "back of the envelope" calculation than a rigorous proof. The main point is, that for a certain system, the cost of obtaining a set of trajectories with a given statistical accuracy is fixed with ab initio MD, as only the dynamically relevant parts of the PES are calculated. 

With what is here called "classical MD" (but also applies to "quantum dynamics" and "wave packet" methods), the whole PES is computed in advance, and this cost is system dependent (scales with $3N - 6$ for nonlinear systems); the individual trajectories over this PES are then calculated comparably quickly.

The ratio of the two scalings is $\frac{10^{3N-6}}{10^{M+n}}$, increasing with system size (making ab initio MD favourable) and decreasing with required statistical accuracy (making classical MD favourable).