Saturday, August 14, 2010

On P not equal NP

Last week a researcher from HP Research Lab, by the name of Vinay Deolalikar, notified the universe that he succeeded to prove that P is not equal NP, which has been an open problem for many years, many people has set to work on his more than 100 pages proof, and some claimed on finding fundamental flows, as a result Deolalikar notified that he is fixing some parts and will re-post an updated version soon. Many people are skeptic, but we'll have to wait and see.

Some observations about it:

  1. The current Web 2.0 media -- Blogs, forums, social networks, is the frontier in which this entire discussion is being made, in a way there is a public peer review that is typically in scientific publications is being handled behind the scenes and don't make public. This is an interesting phenomenon. We see public reviews of books on the Amazon site, but public peer review on unpublished scientific work is rare to go public; I guess that this is currently reserved to VIP papers.
  2. The scientific who did this work is from an industrial research lab and not from the academia, somewhat surprising since the image is that industrial research is interested in system oriented research and not in theory oriented research -- well, the world is not black and white. While research in industry is not in its glory period these days, it still attracts high quality scientists who prefer the frame of the private sector on the academic one.
  3. People generally assume that P is not equal NP, and thus for many of the NP problems which have a need to be resolved in reality, there are devised methods and heuristics to obtain good enough solutions for most realistic scenarios. A proof that this assumption is true will have a huge theoretical value, but not a huge practical value, since it will not provide any insight of how to improve the solutions. Of course, if somebody will prove that P = NP it will have a pragmatic value, if it will show how to solve all the NP problems in polynomial time.
  4. While the fate of this proof has not determined yet, I wish luck to Deolalikar, I like daring people.

1 comment:

Rainer v. Ammon said...

Since I became grandpa in June, I'm more interested in the grandfather paradoxon ( and time travel of my first granddaughter if she would kill me before I have met her grandmother and what Stephen Hawkin tells nowadays or see also "Physicists Tame Time Travel by Forbidding You to Kill Your Grandfather"