We recall that the incompressible Euler equations are formally reversible in time, but the only solutions that exist over time are weak turbulent near-solutions and any such solution is irreversible in time because pointwise exponential instability transforms smooth solutions into non-smooth turbulent solutions in finite time with (positive) turbulent dissipation bounded away from zero as resolution in space and time tends to zero.
We know from the book how to compute turbulent solutions u(t) to the incompressible Euler equations from given initial data u(0) at time t = 0 over a period of time (0,T) with polynomial work with respect to space-time resolution. We now consider the problem Q of recovering a given u(0) from observed u(T). We ask if this is possible with polynomial work, that is, we ask if Q is P?
In other words, we ask if it is possible to solve the incompressible Euler equations backward in time with polynomial work?
By the above argument backward solution from u(T) necessarily produces substantial turbulent dissipation backward in time, which makes recovery of initial data u(0) impossible, since u(T) results from u(0) with substantial turbulent dissipation in forward time. It is thus impossible to recover u(0) from u(T) by computing backward in time, if a sufficiently small tolerance (which does not need to be very small) for the recovery is chosen.
We conclude that it is impossible to recover u(0) from u(T) by solving the Euler equations backward in time, independent of the computational work invested, thus that Q is notP.
On the other hand, if we have a candidate for u(0), we can check by solving Euler in forward time if that candidate fits with u(T), that is, we can check Q by polynomial work, that is, Q is NP.
We thus have an example which is NP and notP, that is, a counterexample to P = NP.
Incidently, the above argument includes a solution to the Clay Navier-Stokes problem: Globally smooth solutions do not exist for small viscosity, only turbulent non-smooth solutions do
We now add more details to the argument:
The nature of the Euler equations as being formally reversible in time makes the above argument fundamentally different from a similar argument for the heat equation which represents an easy-forward difficult-backward problem, which can be solved without too much work by Tychonov regularisation and iteration/shooting forward in time. For the heat equation solution complexity decreases with time (exponential stability), while for the Euler equations solution complexity increases with time (exponential instability-stability, from laminar to turbulent), which (most likely) prevents solution by Tychonov regularisation and forward shooting.
It is thus the very specific nature of the Euler equations with both pointwise exponential increase and decrease of perturbations generating turbulent solutions existing over long time without blow-up, which presents to us a computational problem which is easy to check (NP) but difficult to solve (notP) as a counterexample to P = NP.
Computational Euler can be formulated as a discrete n-bit problem, which is not "man-made" in the sense of expressing the formidable complexity of physical turbulent flow, to be compared with the attempts to design man-made n-bit counterexamples of P = NP (searching, traveling salesman, prime number factorization), which have not been successful so far, probably because they lack some of the richness of Computational Euler.
My conjecture is thus that Computational Euler Backward is a problem which is NP (easy to check) but notP because (i) time-stepping backward is impossible with any amount of work, (ii) iterative forward shooting requires exponential work because of the richness/complexity of turbulent Euler solutions, and there are no thinkable algorithms beyond (i) and (ii) which can be P.
PS1 It is natural to compare the Euler equation with (a) the heat equation and (b) the Lorenz equations. The heat equation forward/backward is exponentially stable/unstable and so notP by (i) but P by (ii) and thus does not offer a counterexample to P = NP. The Lorenz equations are exponentially unstable both forward and backward and thus do not offer a counterexample to P = NP. The Euler equations are both stable and unstable both forward and backward thus seem to offer a counterexample to P = NP.
PS2 Let me illustrate that the Euler equations though formally time reversible, in reality are time irreversible with major defect. Consider the flow around a circular cylinder with flow inflow from left depicted in blue in the below and observe that the solution is non-symmetric in the flow direction with the flow being laminar before attachment to the left of the cylinder and turbulent after separation to the right. Consider now reversing velocities at a final time T with the intention to recover the solution at an earlier time 0 < T, which is the same as reversing time to recover the state at time 0 from the state at time T :
A corresponding recovered solution obtained by time stepping the Euler equations is depicted in red below and shows a solution analogous to the forward solution in blue, but a red solution which is qualitatively different from the blue. The necessary creation of turbulence at separation thus makes solutions with opposite inflow velocities qualitatively different. We conclude that backward time stepping cannot solve our problem Q of recovering an earlier state from a later.
What remains is then iteration by shooting, and the idea is then that the richness of solutions to the Euler equations will make this impossible with P.
PS3 The P = NP or NP = P? problem has the form of a recovery/reconstruction problem with a forward problem which is NP (easy to check) and a backward problem, which if notP would be a counterexample to NP = P. This is the setting in cryptography based on problems which in forward form are easy to solve (check if a given prime factorisation of a given natural number is correct), but difficult in backward form (given a natural number, find its factorisation into prime numbers).
The difficulty in the setting go P = NP? of a man-made problems of this nature, is to show that there is no algorithm for prime factorisation which is P, and there seems to be no way to show that this is impossible, since the number of possible algorithms is limitless because the factorisation problem itself has such a simple nature, following the logic that the simpler the problem the more algorithms are possible.
In the setting of the Euler equations, we turn this around and thus consider a problem which is very complex with the idea that the number of possible algorithms then may be bounded (above 2) thus making exhaustive test possible.
PS4 Let me detail PS1 a bit. Consider the following characteristics of a recovery problem Q of identifying initial data u(0) from solution u(T) at later time T, in the setting (a) heat equation, (b) Lorenz and (c) compressible Euler:
- (a): Forward stable - backward unstable: Gross features of u(0) can be recovered from u(T) by solving backward in time by time stepping or shooting and thus Q is P. Damping of all fine details in forward time. Many u(0) give almost the same u(T), or, u(0) is not very specific.
- (b): Forward stable-unstable and backward stable-unstable: Both check and recovery/solve of gross features requires exponential work and thus Q not NP. No damping of some fine details in forward time.
- (c) Forward stable-unstable and backward unstable-stable as in (b), but with gross features of u(T) computable from u(0) with P, thus with Q as NP. The question is now if recovery of u(0) from u(T) is possible as P? We know that backward time stepping is notP, and we now ask if also shooting is P as in (a)? The difference from (a) is that some fine details of u(0) are not damped in forward time and thus may influence gross features of u(T). Recovery of u(0) thus appears to demand recovery of not only gross features of u(0) but also fine details, and to recover fine details by shooting may well so difficult that it is notP. In this case few u(0) give almost the same u(T) and so recovery is much more difficult than in (a).
We have thus nailed the problem of P = NP to a question of recovery of initial data u(0) for compressible Euler from solution data u(T) at later time T. We have noticed that fine details of u(0) may influence gross features of u(T) and recovery of u(0) thus demands recovery of fine details of u(0), that is a very specific u(0), and the conjecture is then that this problem is notP.
PS5 In a setting of authentication the problem Q may take the following form: Choose an initial state u(0) of complex nature and solve the Euler equations forward with a specified discretisation in space-time (G2 with certain mesh) to obtain a final state u(T). Use u(0) as key to a lock consisting of G2 with mesh and u(T). Knowledge of u(0) allows opening the lock by solving Euler with G2-mesh to get u(T). Here G2-mesh and u(T) may be public and the idea is that finding the key u(0) from public data will be exponentially difficult, while testing if a key candidate works or not is polynomially easy.
PS6 Alternatively, G2-mesh can be seen as a cryptographic hash function with property of computing from a given input or message u(0) an output or hash value u(T), such that (i) u(T) is easy to compute from u(0), (ii) it is difficult to recover u(0) from u(T), (iii) small change of message will give large change of hash value, (iv) it is difficult to find two messages with the same hash value.
PS7 Turbulent solutions of the Euler equations express the 2nd law of thermodynamics as describing an irreversible process in time, where the irreversibility is a result of turbulent dissipation which is substantial and unavoidable. Exact solutions of the Euler equations (such as potential solutions) are reversible in time but are unstable and thus are both unphysical and uncomputable under finite precision. Turbulent Euler solutions of the Euler equations represent a computational process/algorithm with substantial irreversibility in time which is unavoidable and thus gives the 2nd law a rationale without the ad hoc assumptions of diffusion or tendency to disorder or stochastics which makes the 2nd law in standard form a mystery:
The irreversibility of Euler solutions is the result of the impossibility of computing exact solutions, and the necessary presence of turbulent dissipation in computable weak solutions. It is natural that a counterexample to P = NP can be found in this setting with the impossibility expressing notP and the possibility NP.
PS5 In a setting of authentication the problem Q may take the following form: Choose an initial state u(0) of complex nature and solve the Euler equations forward with a specified discretisation in space-time (G2 with certain mesh) to obtain a final state u(T). Use u(0) as key to a lock consisting of G2 with mesh and u(T). Knowledge of u(0) allows opening the lock by solving Euler with G2-mesh to get u(T). Here G2-mesh and u(T) may be public and the idea is that finding the key u(0) from public data will be exponentially difficult, while testing if a key candidate works or not is polynomially easy.
PS6 Alternatively, G2-mesh can be seen as a cryptographic hash function with property of computing from a given input or message u(0) an output or hash value u(T), such that (i) u(T) is easy to compute from u(0), (ii) it is difficult to recover u(0) from u(T), (iii) small change of message will give large change of hash value, (iv) it is difficult to find two messages with the same hash value.
PS7 Turbulent solutions of the Euler equations express the 2nd law of thermodynamics as describing an irreversible process in time, where the irreversibility is a result of turbulent dissipation which is substantial and unavoidable. Exact solutions of the Euler equations (such as potential solutions) are reversible in time but are unstable and thus are both unphysical and uncomputable under finite precision. Turbulent Euler solutions of the Euler equations represent a computational process/algorithm with substantial irreversibility in time which is unavoidable and thus gives the 2nd law a rationale without the ad hoc assumptions of diffusion or tendency to disorder or stochastics which makes the 2nd law in standard form a mystery:
The irreversibility of Euler solutions is the result of the impossibility of computing exact solutions, and the necessary presence of turbulent dissipation in computable weak solutions. It is natural that a counterexample to P = NP can be found in this setting with the impossibility expressing notP and the possibility NP.
Inlägg
Inga kommentarer:
Skicka en kommentar