Thaindian News

London, Aug 14 (ANI): 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)