fredag 15 april 2016

Counterexample to P = NP with Relation to 2nd Law

Let me here present the counterexample to P = NP from the previous post in more concise form.

We consider the Algorithm of solving the incompressible Euler equations over a time interval (0,T) by the stabilized finite element method G2.  We observe that solutions are turbulent with turbulent dissipation which remains substantial (positive) as the discretisation is refined.

We know that exact laminar solutions (such as potential solutions) of the Euler equations are unstable and as a result all solutions turn turbulent over time. We know that given an initial state u(0), the Algorithm delivers a final state u(T) at later time T > 0 with local mean-values of u(T) of certain size computable to a certain precision with polynomial work.

We pose the problem Q of computing the initial state u(0) from a computed final state u(T).  We ask of this can be done with polynomial work, that is, we ask if Q is P?

For any reconstruction candidate v(0), the corresponding v(T) can be computed with polynomial work, which allows check if v(T) is sufficiently close to u(T) to say that v(0) is a acceptable reconstruction of u(0). In other words, Q is NP.

We know that solving the Euler equations backward in time, cannot lead to an acceptable  reconstruction of u(0) from u(T) if the tolerance is small enough, because the substantial turbulent dissipation necessarily being introduced computing u(T) from u(0) in forward time, cannot be reversed. Instead additional substantial turbulent dissipation is introduced in backward time, independent of the work invested.

This means that a substantial gap will remain between original image u(0) and any reconstruction v(0) computed backward in time from u(T), independent of the work invested in the backward process.

Q is thus notP if Q is backward time-stepping. Is it possible to reconstruct u(0) in some other way?
Simply testing all u(0) is certainly exponential and the question is then if it is possible to restrict the testing or shooting? The complexity of turbulent flow with each preimage u(0) giving a computed image u(T) of great local mean-value variability, means that substantial restriction seems impossible and so Q appears to be notP by simply testing all possibilities or shooting in all directions.

The remaining possibility would be some iterative method with further restriction of testing by successive improvement of shooting. We thus ask if there is some thinkable iterative method to solve an identification problem of solving an equation of the form Eu(0) = u(T) with Eu(0) the solution of the Euler equations with initial data u(0) evaluated at time T.

Here E represents an operator which is locally exponentially both unstable and stable, and any attempt to solve such an equation iteratively would seem to fail because the spectrum (of a linearization) of E will be spread over the whole complex plane.

We conclude that solving Q by (a) backward time stepping, (b) restricted guessing, (c) iterative shooting, appears to be clearly notP.  Are there any other possibilities? If not, then Q would be notP.

We summarise: Turbulent Euler solutions have the very special property of:
  1. Unavoidable substantial irreversibility from unavoidable substantial turbulent dissipation, independent of resolution.
  2. Great output variability resulting from local exponential instability-stability. 
  3. Forward problem P up to local mean values.
  4. Backward time stepping notP because of substantial irreversibility.
  5. Iterative shooting notP because of spectrum with no restriction. 
Altogether, turbulent Euler appears to give a counterexample to P = NP.

At the same time it gives meaning to the 2nd Law as an easy-forward and difficult-backward problem, which is not based on ad hoc introduction of diffusion or probability (which is the common way of giving "meaning" to the 2nd Law).

At the same time turbulent Euler gives a counterexample to the Clay Problem of global smoothness of Navier-Stokes. 

The Euler equations thus represent a most remarkable mathematical problem, which cannot be solved exactly, but in computational form gives both meaning to the 2nd law and shows limits of computation and mathematics.

It is perhaps not so surprising that several seemingly unrelated and seemingly very difficult problems,  all have a common answer relating to turbulence as an observable phenomenon of reality, which cannot be simply an unresolvable mystery for ever hidden to human understanding.

I have tried over a long to get some understanding for the issues presenting themselves in the Euler equations, without too much success:
  • I appears that mathematicians are not keen to bring in stability or well-posedness, although the mathematician Hadamard told them to do that, and the result is dead-lock. 
  • It appears that computer scientists prefer integers before real numbers and physics, and the result is a dead-lock with man-made algorithms. 
  • It appears that physicists prefer to speculate about multiversa and quantum foam beyond rationale.
  • It appears that fluid mechanicians are stuck in infinitely thin Prandtl boundary layers beyond  computability.   
But there is hope: reality is there to discover and understand.

Inga kommentarer:

Skicka en kommentar