London: Indian-origin computer scientist Vinay Deolalikar’s answer to P vs. NP has ‘potentially fatal flaws’, some scientists have pointed out.
The claim to proof had created quite a buzz amongst mathematicians and scientists on the Internet, since it’s one of the most complex problems of the world, as declared by Clay Mathematics Institute in Cambridge, Massachusetts.
Roughly speaking, P is the set of problems that can be computed quickly, while NP contains problems for which the answer can be checked quickly.
Deolalikar claims to have proven that P is not equal to NP, which if true, would impose severe limits on what computers can accomplish.
However, Neil Immerman of the University of Massachusetts said that he found a "serious hole" in Deolalikar``s paper.
According to New Scientist, Deolalikar attempts to show that some problems are in NP but not in P (and thus that P not equal to NP) by invoking another mathematical set known as FO(LFP). Immerman says that this set can``t be used in this way, given other methods deployed in the proof.
Looking at the criticism positively, it might result in a correct solution.
A flurry of online activity on a Wiki page indicates blogs and wikis rivalling blackboards and journals – a potentially positive outcome, even if P vs. NP remains unresolved.
"The internet is making a huge difference to the way mathematicians operate. A process that might have taken weeks and weeks has taken place extremely quickly,” said Timothy Gowers of the University of Cambridge. (ANI)
First Published: Saturday, August 14, 2010, 13:07