rawwellのブックマーク - はてなブックマーク

A Proof That P Is Not Equal To NP?
A serious proof that claims to have resolved the P=NP question. Vinay Deolalikar is a Principal Research Scientist at HP Labs who has done important research in various areas of networks. He also has worked on complexity theory, including previous work on infinite versions of the P=NP question. He has just claimed that he has a proof that P is not equal to NP. That’s right: . No infinite version.
rawwell 2010/08/23
リンク
Update on Deolalikar’s Proof that P≠NP
rawwell 2010/08/22
I think there are several levels to the basic question “Is the proof correct?”: 1. Does Deolalikar’s proof, after only minor changes, give a proof that P != NP? 2. Does Deolalikar’s proof, after major changes, give a proof that P != NP? 3. Does the general proof strategy of Deolalikar (explo
リンク
Issues In The Proof That P≠NP
Some further comments into the recent claimed proof that P is not equal to NP Yuri Manin is a great mathematician, who has worked in various areas and also is well known for his many excellent expository works. He has won numerous prizes, including the Nemmers Prize in Mathematics in 1994, and the Cantor Medal in 2002. One of his quotes is: A proof only becomes a proof after the social act of “acc
rawwell 2010/08/22
リンク
1