måndag 4 april 2016

P = NP?

The IT guru Donald Knuth has spoken and said that P = NP:
  • I've come to believe that P=NP, namely that there does exist an integer M and an algorithm A will solve every n-bit problem belonging to the class NP in $n^M$ elementary steps.
  • Some of my reasoning is admittedly naïve: It's hard to believe that P≠NP and that so many brilliant people have failed to discover why.
Knuth then continues to say that the question itself, P = NP? as one of the Clay problems, is not very interesting:
  • My main point, however, is that I don't believe that the equality P=NP will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M.
Knuth here expresses one of the main points I have been preaching to students, that quality without quantitative measure is meaningless:
  • to distinguish between exponential and polynomial growth without careful quantitative measure, may be meaningless. 
  • to define limit in terms of $\epsilon$ and $\delta$ without specifying the dependence of $\delta$ upon $\epsilon$ in quantitative form, may be meaningless. 
But Knuth's belief that anyway, whatever it means that P = NP, appears to result from a belief that the number of possible algorithms is so incredibly large that it is impossible to say that that there is no algorithm that does not solve a given problem in polynomial time, whatever that means.

Another approach is to consider a specific problem, for exemple solving the heat equation backward in time, which is believed to be exponentially difficult, compared to solving the heat equation forward in time, which  is known to be polynomial in time. 

The number of known algorithms for the backward heat equation is two: 
  1. Backward time stepping (exponential)
  2. Iterative solution based on forward time stepping (requires stabilisation). 
The instability of the backward heat equation means that 1 is exponential, and depending on how solution tolerance/stabilization is specified, also 2. may come out to be exponential, I guess. 

The question is then if there are other thinkable methods for solving the backward heat equation? 
How to prove such a thing? What is a thinkable method? What says that the number of possible algorithms is large? Isn't it the other way around? That possible algorithms are few?

The P=NP problem is similar to another Clay problem, that on Navier-Stokes equations, in the sense that the quantitative measure needed to make the problem meaningful in the sense of Knuth, is lacking. Thus, at least two of the Clay mathematical problems appear to be meaningless as formulated, and one may ask what that says about contemporary mathematics, or about Clay?  

Inga kommentarer:

Skicka en kommentar