Comparing the complexity of Einstein's field equations with the Navier-Stokes equations I know litte about the Navier-Stokes equations, but it seems to me that questions related to Navier-Stokes are more fundamental (e.g. do solutions exist for a set of initial conditions) than the ones that are usually aked for the equations of gravity.
Also, a lot of non-linear solutions for general relativity are known and classified according to their symmetries (Stephani, et al.: Exact Solutions of Einstein's Field Equations). Do similar classifications exist for known solutions of the Navier-Stokes equations?
Is it possible to give arguments, why one set of equations is more difficult than the other, if this is actually the case?
 A: 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.


Abstract

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.
