@ryanlpeterman: 哥德尔奖得主对P vs NP的逆向观点："My point is that we really don't understand polynomial time computation…

X AI KOLs Following 2026/07/01 15:18 新闻

p-vs-np complexity-theory theoretical-computer-science godel-prize interview algorithms

摘要

哥德尔奖得主Ryan Williams对P vs NP提出了逆向观点，认为我们对多项式时间计算的理解仍然肤浅且充满惊喜，他将P≠NP的信心定在80%。

哥德尔奖得主对P vs NP的逆向观点："我的观点是，我们对多项式时间计算的理解并没有自己想象的那么深刻。而且总有惊喜。比如，在算法的力量方面，人们不断发现一些算法，简直……令人惊讶。就是……什么？怎么会这么快？这种情况一再发生。所以，是的，我认为这让我把它定在80%，因为我越想越觉得自己不太理解。" @rrwilliams

查看原文

查看缓存全文

缓存时间: 2026/07/01 16:14

哥德尔奖得主对 P vs NP 问题的逆势观点：“我的意思是，我们实际上并不像自己以为的那样理解多项式时间计算。

而且总有意外发现。比如，算法的力量中，人们不断找到令人惊讶的算法……简直不可思议。什么？

你怎么能搞出那么快的算法？

这种事反复发生。所以，我觉得这让我把概率定在 80%，因为我想得越多，就越觉得自己了解得少。“ @rrwilliams

Ryan Peterman (@ryanlpeterman)： Ryan Williams (@rrwilliams) 是 MIT 教授，理论计算机科学领域的哥德尔奖得主。我对他进行了一次访谈，从他的工作聊起，首先问了他一道热门的 LeetCode 题（3SUM）。

本期内容：

• 比流行解法更快地解出 LeetCode 题