you ignored to see the words from knuth followed:Three or four years ago, ...



所有跟贴·加跟贴·新语丝读书论坛http://www.xys.org/cgi-bin/mainpage.pl

送交者: gentoo 于 2006-2-28, 19:21:30:

回答: that's Andrew Yao, 姚期智. Andy is a nickname for Andrew. 由 steven 于 2006-2-28, 19:15:32:

Three or four years ago, there was a paper in a Chinese journal of computer science and technology by a professor who claimed he could solve an NP-hard problem in polynomial time. The problem was about cliques, and he had a very clever way to represent cliques. The method was supposedly polynomial time, but it actually took something like n12 steps, so you couldn't even check it when n equals 5. So it was very hard to see the bug in his proof. I went to Stanford and sat down with our graduate students, and we needed a couple of hours before we found the flaw. I wrote the author a letter pointing out the error, and he wrote back a couple of months later, saying, "No, no, there is no error." I decided not to pursue it any further. I had done my part. But I don't believe it's been solved. That's the most mind-boggling problem facing theoretical computer science, and maybe all of science at the moment.




所有跟贴:


加跟贴

笔名: 密码(可选项): 注册笔名请按这里

标题:

内容(可选项):

URL(可选项):
URL标题(可选项):
图像(可选项):


所有跟贴·加跟贴·新语丝读书论坛http://www.xys.org/cgi-bin/mainpage.pl