送交者: 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.