Computer scientist Vinay Deolalikar claims to have solved maths riddle of P vs NP - Telegraph

Quote:

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.”

__________________
Standard disclaimer: the disgusting statements contained in this post are the views of the poster, and unless specified do not represent the views of the moderators or the site's owners.

Quote:

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.

But, to a degree, creating timetables for, say, teachers fall under that? You got kids who need to attend a series of module and they should not conflict while also creating (fairly) coherent timetables for teachers (who have their own constraints). Is it a matter of scale? If so, how do big departments do it?

Quote:

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.”

Balsy. I like that Scott Aaronson.

__________________
Unless otherwise specified, I am posting as a regular poster. When I will act as a mod, I'll make sure you're in no doubt.