对百万美元逻辑问题进行民意调查


雅各布·阿隆(Jacob Aron)计算机科学中最大的问题仍然没有得到解决,但研究人员比以往任何时候都更有信心答案应该是什么一项新的民意调查揭示了对P与NP问题的看法,其解决方案将回答有关计算的基本问题 - 并获得100万美元的解决方案计算机科学家根据问题需要花费多少时间来解决问题 P是一类“简单”问题,可以在相对较短的时间内通过算法解决 NP是一类易于检查的问题 - 如果给出答案,您可以在短时间内验证 P类中的所有问题也都在NP中,但是不知道所有NP问题是否也在P中如果是,那么P = NP,可能会产生广泛的后果使用正确的算法,可以快速解决所有NP问题,包括各种现实问题一个例子是旅行商问题,找到每次只访问一次城市列表的最短路线,这在物流领域至关重要否则,P≠NP并且许多问题从根本上难以解决来自马萨诸塞州剑桥的克莱数学研究所的证明无论如何价值100万美元 2002年,马里兰大学帕克分校的计算机科学家威廉·加斯塔克(William Gasarch)对100名研究人员进行了调查,其中61%认为P≠NP只有9%的人认为相反,其余人则表示他们不知道或者问题无法解决现在,Gasarch已经与150多名受访者重新进行了调查,并发现P≠NP的​​支持者高达81%试图证明P≠NP在2010年成为头条新闻,但结果证明是错误的 Gasarch说这不太可能影响人们的意见,但确实让他们谈论了这个问题相反,这种转变可能是因为,尽管经过了10年的努力,计算机科学家却未能找到能让他们解决所有NP问题的快速算法无论哪种方式,我们可能需要等待证明在早先的民意调查中,62%的受访者表示会在2100年之前出现答案,但现在已经缩减至53% Gasarch认为P≠NP,证明需要200到400年完整的民意调查结果将于今年晚些时候在计算机协会的算法和计算理论特别兴趣小组上发布更多关于这些主题:
  • 首页
  • 游艇租赁
  • 电话
  • 关于我们