Knuth提到的这个中国人是谁?



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

送交者: gentoo 于 2006-2-28, 19:10:03:

姚期智果然在解决NP=P问题。
但是Knuth提到的这个中国人是谁?

Question: Do you know whether “P equals NP”
has been proved? I heard a rumor that it has.
Knuth: Which rumor did you hear?
Question: One from Russia.
Knuth: From Russia? That’s new to me. Well, I
don’t think anybody has proved that P equals NP
yet. But I know that Andy Yao has retired and
hopes to solve the problem in the next five to
ten years. He is inspired by Andrew Wiles, who
devoted several years to proving Fermat’s Last
Theorem. They’re both Princeton people. Andy
can do it if anybody can.
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