P≠NP?这对计算能力来说是个坏消息

2017-03-05 10:03:38

理查德艾尔维斯计算机科学中最大的问题已经解决了吗 8月6日,位于加利福尼亚州帕洛阿尔托的惠普实验室的数学家Vinay Deolalikar发送了一份名为“P≠NP”的论文草稿这种简洁的断言可能会对计算机解决多种问题的能力产生深远的影响它也回答了Clay数学研究所的七个千年奖问题之一,所以如果事实证明是正确的,Deolalikar将获得100万美元的奖金 P与NP的问题涉及计算机完成任务的速度,例如将数字分解有些任务可以合理快速地完成 - 从技术角度来说,运行时间与输入大小的多项式函数成正比 - 这些任务在P类中如果可以快速检查任务的答案,那么它在NP类中因此,如果P = NP,则可以快速完成可以快速检查的每个问题这一结果将对互联网安全产生巨大影响,因为很难将非常大的数字分解是我们保护数据免受黑客攻击的主要手段但Deolalikar说这不是它的方式他的论点围绕着一个特定的任务,即布尔可满足性问题,它询问逻辑语句的集合是否都可以同时为真,或者它们是否相互矛盾这被认为是NP问题 Deolalikar声称已经证明没有程序可以从头开始快速完成它,因此它不是P问题他的论点涉及统计物理学的巧妙运用,因为他使用的数学结构遵循许多与随机物理系统相同的规则如果结果如此,那将证明P和NP这两个类别不相同,并对计算机可以完成的任务施加严格限制 - 这意味着许多任务可能从根本上,不可简化地复杂化对于某些问题 - 包括因子分解 - 结果并没有明确说明它们是否可以快速解决但是,一个名为“NP-complete”的巨大子问题将注定失败一个着名的例子是旅行商问题 - 找到一组城市之间的最短路线可以快速检查这些问题,但如果P≠NP,则没有可以从头开始快速完成它们的计算机程序复杂性理论家对Deolalikar的草稿给予了好评,但是当最终版本在一周内发布时,检查它的过程将会加剧更多关于这些主题: