punjabi_khota Posted August 10, 2010 Posted August 10, 2010 Did you guys read about it ? http://www.networkworld.com/news/2010/080910-hp-researcher-claims-to-crack.html HP Labs principal research scientist Vinay Deolalikar has posted what he claims is a solution to what is widely known as the P versus NP problem. So intractable is this problem that the Clay Mathematics Institute has vowed to award the person who solves it US$1 million. It is one of only seven problems, collectively known as the Millennium Prize Problems, the institute has offered this bounty for. One of the seven, the Poincaré conjecture, was officially solved in 2006.
Nova Posted August 10, 2010 Posted August 10, 2010 THis is great news. Now independent verification by other mathematicians will start. The Poincare conjecture took almost a year to be verified....
flamy Posted August 10, 2010 Posted August 10, 2010 saw this on ur fb, u feckin geek :mad: didnt want to comment there, lest i be ridiculed like u :((
b555 Posted August 10, 2010 Posted August 10, 2010 and the guy who has solved poincare conjucture gregory prerelman lives in russia , has stopped doing mathematics ,didnt collect his fields medal (highes honour for a mathematician), didnt even take his 1Million prize he is now jobless andlives with his mother and sister
punjabi_khota Posted August 10, 2010 Author Posted August 10, 2010 saw this on ur fb, u feckin geek :mad: didnt want to comment there, lest i be ridiculed like u :(( my friend posted it there...I just commented..:cantstop: :finger: This is big news (if confirmed), but I bet a lot of people were hoping it to turn out the other way...If P=NP, that would have meant that most "hard" problems in CS have a easier solutions, and people just haven't looked hard enough. But as it stands now, it means there are some hard problems for real.
Nova Posted August 10, 2010 Posted August 10, 2010 and the guy who has solved poincare conjucture gregory prerelman lives in russia , has stopped doing mathematics ,didnt collect his fields medal (highes honour for a mathematician), didnt even take his 1Million prize he is now jobless andlives with his mother and sister Some geniuses are eccentric. Perelman should have collected the $1 million prize and given half of it to Hamilton, who he thought deserved as much recognition. There is too much politics and back stabbing in the research community sometimes.
b555 Posted August 10, 2010 Posted August 10, 2010 Some geniuses are eccentric. Perelman should have collected the $1 million prize and given half of it to Hamilton' date=' who he thought deserved as much recognition. There is too much politics and back stabbing in the research community sometimes.[/quote'] yup, everything doesnt seem to be as clear as it always appears to be one main factor- effing jealousy that ruins many things :((
seedhi Posted August 10, 2010 Posted August 10, 2010 Did you guys read about it ? http://www.networkworld.com/news/2010/080910-hp-researcher-claims-to-crack.html HP Labs principal research scientist Vinay Deolalikar has posted what he claims is a solution to what is widely known as the P versus NP problem. So intractable is this problem that the Clay Mathematics Institute has vowed to award the person who solves it US$1 million. It is one of only seven problems, collectively known as the Millennium Prize Problems, the institute has offered this bounty for. One of the seven, the Poincaré conjecture, was officially solved in 2006. Very early to celebrate. The general feeling among the community as far as I can see is that there are some issues with the proof. The whole thing is beyond my scope to read, so cant say anything definte myself but some issues are discussed on Dick Lipton's blog http://rjlipton.wordpress.com/ .
seedhi Posted August 10, 2010 Posted August 10, 2010 my friend posted it there...I just commented..:cantstop: :finger: This is big news (if confirmed), but I bet a lot of people were hoping it to turn out the other way...If P=NP, that would have meant that most "hard" problems in CS have a easier solutions, and people just haven't looked hard enough. But as it stands now, it means there are some hard problems for real.Really, that would surprise me since P=NP would imply that computers would basically be able to do a lot more, much more efficiently - leading to massive job losses amongst engineers, scientists, mathematicians.
triam Posted August 10, 2010 Posted August 10, 2010 Very impressive if the solution is validated by other mathematicians. This is one of the problems which seem so easy and intitutive to humans but proving it is another matter.
punjabi_khota Posted August 10, 2010 Author Posted August 10, 2010 Really' date=' that would surprise me since P=NP would imply that computers would basically be able to do a lot more, much more efficiently -[b'] leading to massive job losses amongst engineers, scientists, mathematicians. I don't think so :dontknow: My limited understanding says that: P=NP would mean is that there are polynomial time algorithms to solve problems so far thought to be only having exponential time algos..but to find those algos, you would need the scientists/engineers etc. One thing that immediately comes to mind is cryptography., which for all practical purposes assume P!=NP (or else the problem of factorizing a large number into 2 primes could be solved in poly time..in theory..it could be n^999999 but still)..
seedhi Posted August 11, 2010 Posted August 11, 2010 I don't think so :dontknow: My limited understanding says that: P=NP would mean is that there are polynomial time algorithms to solve problems so far thought to be only having exponential time algos..but to find those algos, you would need the scientists/engineers etc. One thing that immediately comes to mind is cryptography., which for all practical purposes assume P!=NP (or else the problem of factorizing a large number into 2 primes could be solved in poly time..in theory..it could be n^999999 but still)..Oh no you are mistaken. If there is a polynomial time algorithm for any problem which is NP-complete it instantly (i.e. with very little effort, by Cook's Theorem) will give you a polynomial time algorithm for all problems in NP (=P). The only issues would be optimization as far as the running time (say from n^5 to n^4). But that is not the end of the story. The entire polynomial hierarchy would collapse - i.e. computers would be able to generate statements of (a large class of) mathematical theorems and then prove/disprove them efficiently, thereby eliminating the very need of human mathematicians for many problems. Crytography would die, the banking system would collapse. Last, but not the least P=NP would mean my thesis would become worthless :(( as it is based on P!=NP. As far as Vinay Deolalikar's claim is concerned, it seems it has some serious issues. He has removed all references to it from his webpage, so possibly he is going to withdraw the claim. Or maybe it is still salvageable. Let us see.
b555 Posted August 11, 2010 Posted August 11, 2010 coming to hear theproof got some hype and less substance
THX_1138 Posted August 11, 2010 Posted August 11, 2010 need a week to read up on this... have no idea what on earth this is! suggested reading?
b555 Posted August 11, 2010 Posted August 11, 2010 need a week to read up on this... have no idea what on earth this is! suggested reading? not joking but wikipedia is a good start
The Outsider Posted August 11, 2010 Posted August 11, 2010 Interesting, seedhi. Can you explain the notion of what kind of analytical problems could be tackled in the scenario that you described by computers? Or maybe, give some link where such problems are discussed. I was under the same impression as P_K that it would impact only algorithm development and not analytical solutions.
seedhi Posted August 11, 2010 Posted August 11, 2010 Interesting, seedhi. Can you explain the notion of what kind of analytical problems could be tackled in the scenario that you described by computers? Or maybe, give some link where such problems are discussed. I was under the same impression as P_K that it would impact only algorithm development and not analytical solutions.Loosely speaking, if P=NP then it would mean that any reasonable formal proof could be verified to be true/false by a computer in time polynomial in the size of the proof. So suppose I want to prove some theorem. Then I can program a computer to enumerate all proofs (starting from smallest) and try to verify each one efficiently. Now, say there was a proof of size 10 pages, then eventually that proof would be found and verified. It still entails enumeration, but as computing technology gets faster this might be a method to efficiently "automate" theorem proving. This writeup by Stephen Cook discusses the P vs NP question in more detail : http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
Recommended Posts