tisdag 19 april 2016

P=NP? vs 2nd Law vs Turbulent Dissipation

This is a continuation of the argument from recent posts that the 2nd Law expressed by turbulent solutions to the incompressible Euler equations represents a counterexample to P=NP. The basic ingredients are the following:
  1. Exact smooth solutions of the Euler equations such as potential flow are unstable and thus are not computable globally in time under finite precision.
  2. Turbulent weak solutions can be computed globally in time with polynomial work. Such solutions have substantial turbulent dissipation independent of resolution and thus are substantially irreversible in time. More precisely, the irreversibility with substantial turbulent dissipation independent of resolution makes recovery of an initial state u(0) at time 0 from a computed solution u(T) at later time T, impossible with polynomial work.
  3. The problem Q of recovering u(0) from u(T) is thus appears to be notP, while it is possible to check if a recovery candidate v(0) produces u(T) upon solution forward in time with polynomial work.
  4. It is the unavoidable substantial turbulent dissipation which creates substantial irreversibility under polynomial work and thus shows that Q is notP, while forward solution with polynomial work makes Q NP and thus a counterexample to P=NP.
  5. It is the unavoidable substantial turbulent dissipation which is the reality of the irreversibility of the 2nd Law and makes into a dictate, which cannot be escaped with polynomial computational work and thus neither in physical reality, with physics as a form of analog computation with finite precision, which by the necessary limitations of physical reality can only involve polynomial work.  
  6. The connection to physics as analog computation and the 2nd Law as a law of physics as computation, gives the P=NP? problem a more clear meaning by offering a sharp distinction between P=possible=physical and notP=impossible=unphysical, than in the standard setting of polynomial vs exponential growth, which may be impossible to clearly separate in any form of real computation. 
  7. The formulation of P=NP? as the question if it is easy to go forward from a position u(0) to end up at a position u(T), is it then possible to back-track to an initial position v(0) possibly different from u(0) such that going from v(0) will end up X? For example going down a tree branching one way or the other to X, it is possible to back-track to a possibly different initial position forward connected to X. In any case the P=NP? problem has a definite flavour of irreversibility as forward-easy and backward-not easy.  

Inga kommentarer:

Skicka en kommentar