Million Dollar Men

Earlier this year, an eccentric Russian mathematician turned down $1 million for solving a Millennium Prize Problem. Now, an Indian has laid claim to another.

In March this year, the Clay Institute announced that it had awarded a million dollars to the Russian mathematician Grigoriy Perelman for solving the Poincare Conjecture. The conjecture was one of the seven Millennium Prize Problems posed by the institute, problems deemed to be the most perplexing and important in mathematics, and each carried a million dollar award for a solution. Perelman rejected the money. 

This was startling enough for British newspapers to send journalists to Moscow in search of this enigmatic man. “I’m not interested in money or fame,” Daily Mail quoted Perelman as saying through the closed door of his flat, “I don’t want to be on display like an animal in a zoo. I’m not a hero of mathematics. I’m not even that successful; that is why I don’t want to have everybody looking at me.” Unable to speak to Perelman even through his door, a reporter of The Daily Telegraph relied on neighbours to report that ‘his trousers are always too short for his legs, that the balcony to his flat has been left to rot and he fills his time playing table tennis against the wall. Every day they see him walk to a grocery shop at 1.30 pm where he buys the same things: eggs, cheese, spaghetti, sour cream, bread and a kilo of oranges.’

Of course, none of this has much to do with the scale of his achievement. Perelman first proposed his solution in 2002. In 2006, he was awarded the Field’s Medal, an award given once every four years for work completed before the age of forty, which makes it even more selective than the Nobel (which is not awarded in the field of mathematics). He turned that down as well.

Another Field’s Medalist who accepted the award the same year was Terence Tao, a child prodigy who, as a two-year-old, was caught explaining mathematics and English to older children. He said of Perelman’s achievement, “They [the Millennium Prize Problems] are like these huge cliff walls, with no obvious hand holds. I have no idea how to get to the top. [Perelman’s proof] is a fantastic achievement, the most deserving of all of us here, in my opinion.” Open challenges of this kind have been around at least since 1900, when one of the greatest mathematicians of all time, David Hilbert, proposed a set of 23 problems. As the 20th century progressed, work on many of these opened up new areas of mathematics. In May 2000, to celebrate the 100th anniversary of Hilbert’s address, the Clay Institute announced a similar, though smaller, set of problems: the Millennium Prize Problems.  

The first of these to be solved, the Poincare Conjecture, essentially involves the categorisation of shapes in various dimensions under certain criteria. Consider a circle, an ellipse, or for that matter any loop made out of a string. In two dimensions (that is, on a smooth plane), each can be smoothly converted into the other without tearing or stretching (that is, anything that resembles a circle is indeed a circle). It turns out that a similar question about spheres (the generalisation of a circle where each point on the sphere is equidistant from the centre) can be asked in various dimensions. The question was eventually answered in all dimensions but four, which requires an entirely new approach that Perelman has mastered and refined to obtain the result.

Now, Vinay Deolalikar, an Indian computer scientist at Hewlett Packard, and former student of IIT-Bombay, has proposed a solution for another one of the Millennium seven: the P vs NP problem.  Of his IIT-Bombay days, compatriots recall his passion for ragging and astrology, even if it doesn’t quite place him in the same league of eccentricity as Perelman. Eccentricity and genius may not always be connected, but it does remain true that Deolalikar’s proof so far rests on far less certain ground than Perelman’s accomplishment. What Deolalikar has done is tackle a fundamental problem in theoretical computer science. Consider the question: if the solution to a problem is easy to check, then does that mean that the solution is easy to find? The intuitive answer is no. Just think of a jigsaw puzzle. One look at the solution is enough to judge whether it is correct or not, but by no means is it easy to get that solution.

Now, naively (this is not an exact correspondence with the actual problem where it is necessary to define what it means for a solution to be easy to find or easy to check, but conveys its spirit) consider a collection of problems where if the solution is easy to check, the solution is easy to find, and we call it P. Consider another collection of all problems where all we know is that the solution is easy to check, and we call it NP. Is P the same as NP? The jigsaw puzzle leads us to believe that NP is not equal to P. 

 The problem gets interesting when you consider another class of problems within the NP category. This sub-collection is called NP Complete, and what we know is that if any of them has an easy solution, then all of them have an easy solution. Some of the problems classified as NP Complete are scheduling airline flights and laying out microchips on a board. If P were to be the same as NP, these would be amenable to far more efficient solutions than we know of today.

Deolalikar claims to have shown what most mathematicians believe—that P is not equal to NP. But while everyone may agree with this conclusion, the consensus so far is against  Deolalikar’s solution. Terence Tao had this to say about his proof: “I think there are several levels to the basic question ‘Is the proof correct?’: 

» Does Deolalikar’s proof, after only minor changes, give a proof that P not equal to NP? 

» Does Deolalikar’s proof, after major changes, give a proof that P not equal to NP? 

» Does the general proof strategy of Deolalikar … have any hope at all of establishing non-trivial … results?” 

Tao’s answer is ‘no’ for 1, “probably not, unless substantial new ideas are added” for 2, but he concedes that 3 is “still not completely resolved and still worth pursuing”. In the worst case scenario, Deolalikar may have found a new way of looking at the problem. And if he has indeed been successful, terrific. That leaves five Millennium problems to solve.

About The Author

Hartosh Singh Bal