A computer scientist claims to have solved one of the world’s most complex and intrac

[amit27]

Vinay Deolalikar, who works at the research arm of Hewlett-Packard in Palo Alto, California, believes he has solved the riddle of P vs NP in a move that could transform mankind’s use of computers as well as earn him a $1m (£650,000) prize.

P vs NP is one of the seven millennium problems set out by the Massachusetts-based Clay Mathematical Institute as being the “most difficult” to solve
Many mathematical calculations involve checking such a large number of possible solutions that they are beyond the current capability of any computer. However, the answers to some are quick and easy to verify as correct. P vs NP considers if there is a way of arriving at the answers to the calculations more quickly in the first place.

Mr Deolalikar claims to have proven that P, which refers to problems whose solutions are easy to find and verify, is not the same as NP, which refers to problems whose solutions are almost impossible to find but easy to verify.

His paper, posted online on Friday, is now being peer-reviewed by computer scientists.

Scott Aaronson, associate professor of computer science at the Massachusetts Institute of Technology, is so sceptical that he pledged on his blog to pay Mr Deolalikar an additional $200,000 (£125,000) if the solution is accepted by Clay.

He wrote that he could barely afford the sum, but explained: “If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it.”

The P vs NP problem was formalised in 1971 by mathematicians Stephen Cook and Leonid Levin.

To help understand the issue, the Clay Mathematical Institute gives an example in calculating how to accommodate 400 students in 100 university rooms.

It says: “To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice.

“This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a co-worker is satisfactory (i.e., no pair taken from your co-worker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical.

“Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe.

“Thus no future civilisation could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students.

“However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure.”

 

[SMC]

This is one of the toughest things to prove and it would be interesting see if the proof stands. From what I am seeing in the coverage, the proof seems to have holes and is not correct.

 

[amit27]

This is one of the toughest things to prove and it would be interesting see if the proof stands. From what I am seeing in the coverage, the proof seems to have holes and is not correct.

Yep its already causing controversy but if this claim does turn out to be genuine it could change the world 4 eva.

BBC News - Million dollar maths puzzle sparks row

 

[SandsofTime]

Yep its already causing controversy but if this claim does turn out to be genuine it could change the world 4 eva.

Actually, not so much. Its been conjectured that P!=NP so proving it isn't going to bring anything exciting to the table. Now if converse were true i.e. P=NP, that would rock the world

 

[nForce]

P vs NP Problem​

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

Source

The complete paper offered by Vinay Deolalikar can be accessed here.

 

[nForce]

For information to all......one of the famous seven problems laid down by The Clay Mathematics Institute in Cambridge, Massachusetts has already been solved by the Russian Mathematician,Grigory Perelman.The theorem is known as Poincaré's conjecture.He refused to take the award though and preferred to lock himself up in his flat.

Grigory Perelman, the maths genius who said no to $1m​

You are the world's cleverest man. You have solved one of maths' most intractable problems. Do you a) accept a $1m reward, or b) reject the money, barricade yourself inside your flat and refuse to answer the door? The answer, if you are the reclusive Russian genius Grigory Perelman, is b).

The Clay Mathematics Institute in Cambridge, Massachusetts, last week honoured Perelman for his solution to a problem posed almost a century ago by French mathematician Henri Poincaré. The theorem – known as Poincaré's conjecture – involves the deep structure of three-dimensional shapes. It is one of seven elusive challenges set by the institute, each carrying a $1m reward. It took the world's leading mathematicians several years to verify that Perelman had definitively solved the problem in a paper published in 2002.

Perelman, however, doesn't want the cash. This latest snub follows his refusal in 2006 to collect the maths equivalent of an Oscar, the Fields Medal. Perelman is currently jobless and lives with his mother and sister in a small flat in St Petersburg. (He has his own spartan one-bedroom flat, allegedly full of cockroaches, but rarely uses it.)

Perelman refuses to talk to the journalists camped outside his home. One who managed to reach him on his mobile was told: "You are disturbing me. I am picking mushrooms." The handful of neighbours who have seen him paint a picture of a scruffily dressed, unworldly eccentric. "He always wears the same tatty coat and trousers. He never cuts his nails or beard. When he walks he simply stares at the ground, rather than looking from side to side," one told a Moscow newspaper.

"He has rather strange moral principles. He feels tiny improper things very strongly," says Sergei Kisliakov, director of St Petersburg's Steklov Mathematics Institute, where the maths prodigy once worked as a researcher.

According to Kisliakov, Perelman quit the world of mathematics in disgust four years ago. His decision to spurn the Fields Medal may have been driven by a sense that his fellow mathematicians were not worthy to award it. "He severed all contact with the community, and wanted to find a job unrelated to maths," Kisliakov says. "I don't know whether he succeeded in that."