First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could the size of the input vary if the problem was the three dimensions one? Seems not if the number of equations is limited. Could this problem be classifiable in a problem class?

Trying to figure it out...but stuck.

Navier-Stokes problem

P vs NP problem where you can find the formal definition of P and NP problems.

I have been reading the following question, it did not help me, but may help to answer my question. Why is the set for which a decision problem is true called a "language"?


1 Answer 1


Languages are a good way of discussing yes or no questions with a finite bit-length input size. There are plenty of alternatives to languages, in complexity theory! They often have some 'moral equivalence' to languages.

Two important cases are Function problems and Approximation problems.

Function problems give you some bitstring $s$ and you need to compute some output function $f(s)$. Now instead of the set $\mathsf{P}$ of polynomial time languages, you talk about the set $\mathsf{FP}$ of functions that a language can compute in polynomial time. There is also $\mathsf{FNP}$, problems where you can compute the answer if you manage to guess the right 'proof'; $\mathsf{FBPP}$, where you can compute the right answer with probability at least 2/3; and so on.

Approximation problems are sort of a refinement of function problems, where now the input string $f(s)$ is interpreted as a real number (in some standard encoding) and you're asked to give not necessarily the exact number, but to give a number somewhere close to $f(s)$. The input consists of the problem string $s$ together with a precision parameter $\epsilon$. Typically you talk about multiplicative approximation where you need to answer within a factor of $1\pm \epsilon$, or additive approximation where you need to answer within an additive error of $\pm \epsilon$. Some important classes here are $\mathsf{FPTAS}$, see here, which includes problems that you can solve in time $O(n^3 / \epsilon^3)$, for instance; $\mathsf{APX}$, see here, where you can solve in polynomial time as long as $\epsilon > c$ for some constant $c$; and others.

Alright, with that out of the way!

"Solving the Navier-Stokes equations", as a problem, I would generally write down as an approximation problem as follows. The input string gives some finite-size description of the initial state. This would probably be a grid size $n$, where I specify initial pressure and velocity values at each point on the grid. Then we have some agreed-upon encoding to turn this into a continuous function: for instance, third-order polynomial interpolation. This defines an initial state. There is similar data for boundary conditions. Then you give me a time $t$, a point $(x,y,z)$, a query variable that is one of the thre symbols $\{VX,VY,VZ\}$, and a precision $\epsilon$. The problem is then to output the relevant variable (the velocity $VX$, or $VY$, or $VZ$) after evolving the initial conditions for $t$ time, and to output with an additive error $\epsilon$.

The difficulty of the problem would be quantified in terms of different quantities like $n$ (the complexity of the boundary conditions), the precision $\epsilon$, and the time $t$. Difficulty could also be in terms of the Lipschitz constant $K$ of the boundary conditions, or the magnitude $M$ of the initial conditions (if I make all the initial velocities extremely fast, I could make things happen very quickly and the problem might become might harder!), or the energy $E$ of the system, or the worst condition number $\kappa$ reached during solving.

I think people would consider the Navier-Stokes equations to be "polynomial time" if there was an algorithm to solve this, with a runtime like $O(n^{c_1} t^{c_2} \epsilon^{-c_3} K^{c_4} M^{c_5})$, where $c_i$ are all some constants. Equivalently, if it run in $poly(ntKM/\epsilon)$ time.

The differential equations that people generally regard as "well-behaved" all have algorithms of this form. There are some differential equations that compute (say) the answer to an NP-hard problem in a small amount of time -- in the sense that, if you had a poly time algorithm to solve them (in the sense I just gave), that it would imply $P=NP$.

  • $\begingroup$ I thank you very much for your answer. Is it so possible to say that the Navier-Stokes equations problem is not in P? and can it be in NP? $\endgroup$
    – someone
    Nov 9, 2023 at 20:51
  • $\begingroup$ I may have understood that FNP is in NP on Wikipedia. So if the NS problem is in FNP, it is in NP? Like if we consider the NS problem as a decision one like this: is there a solution to the NS problem? $\endgroup$
    – someone
    Nov 9, 2023 at 20:55
  • $\begingroup$ FNP and NP are "morally equivalent" in the sense that are very similar in difficulty, and you can often convert between them in a meaningful way. But they are different types. It would be like taking the set of functions of the form f(x)=m*x+b, and the set of lines of finite slope in the plane. They are naturally equivalent, but one set contains functions, and the other set contains lines (which are sets of points). There's a natural equivalence, but (for instance) I can compose functions, but I can't "compose" lines in the plane; I can take the union or intersection of lines, not functions. $\endgroup$ Nov 10, 2023 at 21:10
  • $\begingroup$ It is entirely possible that Navier-Stokes is in P, or that it is not in P; it also might be in NP, or not in NP. It is possible that it is might be much harder than NP, it could even be EXPTIME complete or even undecidable, as far as I know. The Millenium Prize problem is just proving that the Navier-Stokes equation has a solution at all, which is not known to be true: it is possible that there's a mathematical contradiction inherent in the problem. In the same way that if I give you a set of N linear equations in N variables, it will usually have a solution, but it's possible... $\endgroup$ Nov 10, 2023 at 21:13
  • $\begingroup$ ...that there's a contradiction in the equations I give you, and then there's no solution. So when you talk about the complexity of "solving linear equations", you need to first be confident that a solution exists! In the case of linear equations we have a good understanding of when a solution exists, and how to solve it then. For the Navier-Stokes equation, it's unclear when a solution exists. $\endgroup$ Nov 10, 2023 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.