An interesting perspective on this question could be offered by works on fluid/gravity correspondence.
For example, see this paper:
- Bredberg, I., Keeler, C., Lysov, V., & Strominger, A. (2012). From Navier–Stokes to Einstein. Journal of High Energy Physics, 2012(7), 146, doi:10.1007/JHEP07(2012)146, arXiv:1101.2451.
We show by explicit construction that for every solution of the incompressible Navier-Stokes equation in $p+1$ dimensions, there is a uniquely associated “dual” solution of the vacuum Einstein equations in $p+2$ dimensions. The dual geometry has an intrinsically flat timelike boundary segment $\Sigma_c$ whose extrinsic curvature is given by the stress tensor of the Navier-Stokes fluid. We consider a “near-horizon” limit in which $\Sigma_c$ becomes highly accelerated. The near-horizon expansion in gravity is shown to be mathematically equivalent to the hydrodynamic expansion in fluid dynamics, and the Einstein equation reduces to the incompressible Navier-Stokes equation. For $p=2$, we show that the full dual geometry is algebraically special Petrov type II. The construction is a mathematically precise realization of suggestions of a holographic duality relating fluids and horizons which began with the membrane paradigm in the 70's and resurfaced recently in studies of the AdS/CFT correspondence.
This allows one to establish a “dictionary” relating problems concerning Navier–Stokes equations with problems posed for Einstein equations in a higher dimensional spacetime. As the paper suggests:
… cosmic censorship could be related to global existence for Navier-Stokes or the scale separation characterizing turbulent flows related to radial separation in a spacetime geometry …
On the other hand, not every question that could be asked about Einstein equations is about the near-horizon expansion, so for some rather loose interpretation, the “complexity” of Einstein's field equations (in higher dimensions) is strictly greater than that of Navier–Stokes equations.