新闻二则：P≠NP有望得证 魔方问题告破

    昨天的消息：一位 HP 的研究员 Vinay Deolalikar 宣称自己证明了 NP 问题，得出了 P≠NP 的结论。 P 是否等于 NP ，这是计算机科学领域中最困难的问题之一，也是意义最深远的问题之一，长期以来一直备受争议。如果这个问题获得解决，将会在各个科学领域中引起轰动。 Vinay Deolalikar 的整个证明有 100 多页，详细的论文可以在这里看到：

      http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf

    Stanford 的博士后 randomwalker 看完证明后表示，很多迹象表明，这个证明很有可能是正确的。

     －－－－－－－－－－－－－－－－－－－－－－－－－－－

    今天早晨的消息： Morley Davidson 、 John Dethridge 、 Herbert Kociemba 和 Tomas Rokicki 宣称，他们已经利用计算机，完美地解决了魔方问题。他们验证了，任何一种魔方的初始状态都可以在 20 步以内解出。他们将 43,252,003,274,489,856,000 种初始状态分为了 2,217,093,120 组，再利用对称性和集合覆盖将规模缩小到了 55,882,296 组。他们的程序可以在 20 秒左右求解出一组问题的解法，最终利用 Google 提供的强大的计算机，彻底解决了魔方问题。
    利用组合数学，我们能够证明，存在一种魔方初始状态，它需要至少 18 步才能解决。 1995 年， Michael Reid 找到了一种最少需要 20 步才能获解的魔方初始状态，因而将魔方问题的下界提高到了 20 。此后，数学家们猜想，任意给定一个魔方的初始状态，最多 20 步就能解决。 2008 年， Tomas Rokicki 和 John Welborn 证明了，任意一个魔方初始状态都可以在 22 步以内解决。 2010 年 7 月，这个上界终于降低到了 20 ，从而完成了对魔方最优解问题数十年来的探索。
    详细的研究成果见这里：

      http://www.cube20.org/
 

36 条评论

发表评论




Enter Captcha Here :