P不等于NP。听起来很简单。但如果它是真的，它可能是计算机科学家几十年来一直在努力解决的问题的答案。来自惠普实验室的Vinay Deolalikar已经将其证明副本发送给同行，声称P不等于NP。数学家们正在审查他的工作——这项任务可能需要很长时间。如果他没错，Deolalikar将解决了克雷数学研究所七个千禧年大奖难题中的一个，每个难题的奖金为100万美元。（Grigory Perelman因解决了庞加莱猜想而获得其中一个奖项，但上个月拒绝了奖金。）这到底是怎么回事？首先，一个解释。
P与NP的问题关系到计算机完成任务的速度，例如分解一个数字。有些任务可以很快完成——用技术术语来说，运行时间与输入大小的多项式函数成比例——这些任务属于P类。如果一个任务的答案可以很快得到验证，那么它就属于NP类[New Scientist]。
这个定义相当抽象，所以这里有一个更具体的例子。
克雷想象了一个大学住宿的情况，有400名学生申请了房间，但学校只能容纳100名。必须将100名学生配对入住房间，但学生院长有一份名单，列出了某些学生之间不能同住。可能的配对总数极其庞大——超过宇宙中原子的总数——但解决方案，即最终提交给院长的配对名单，很容易检查错误：如果名单上有一个院长禁止的配对，那就是错误[AOL News]。
因此，如果P等于NP，那就意味着像这种室友匹配一样容易检查的问题，也必须容易解决。但如果Deolalikar是正确的，而且实际上P不等于NP，正如许多数学家已经相信的那样
，那么就不一定如此了。根据麻省理工学院的Michael Sipser的说法，这将具有实际意义。
Sipser……表示，P与NP问题对于加深我们对计算复杂性的理解很重要。“一个主要的应用是在密码学领域，”Sipser说，其中密码的安全性通常由计算任务的复杂性来保证。RSA加密方案，常用于安全的互联网交易——并且是麻省理工学院发明的——“实际上是研究某些数论计算复杂性研究的成果，”Sipser说[MIT News]。
Deolalikar的证明现在可以在线阅读
报道称，他综合了不同学科的策略，证明了一个NP问题——一组陈述是否可以同时正确或相互矛盾——不是一个P问题，因为它易于检查，但任何计算机都无法快速从头开始解决。自该证明在互联网上传播以来，一些数学博主如Scott Aaronson
回应该证明时表示，是的，它很棒，但很可能站不住脚。相关内容：80beats：才华横溢但隐居的俄罗斯数学家不需要你的奖金
80beats：谷歌算法能预测诺贝尔奖得主吗？
DISCOVER访谈：宇宙物理学背后的数学
DISCOVER：2006年十大数学故事
， featured Perelman’s achievement 图片：HP Labs
