adv

计算机搜索产生“最大”的数学证明

数学 超级电脑
pigsrollaroundinthem (39396)发表于 2016年05月31日 15时55分 星期二
来自暴力破解部门
得克萨斯奥斯丁、斯旺西大学和肯塔基大学的三名数学家在超级计算机Stampede的帮助下完成了一个并不优雅的证明,文件大小400TB,这是人类不可能读完的最大数学证明。计算机给出了一个答案,但并没有给出更多的解释,这是计算机辅助证明所带来的哲学上的困惑。研究论文(PDF)发表在预印本网站上。三位数学家解决的是一个布尔可满足性问题,可满足性问题是第一个被证明的NP完全问题。问题是加州圣迭戈数学家Ronald Graham在1980年代提出的,名叫布尔毕达哥拉斯三元数问题:对于自然数集合N={1,2,3,4...},能否将它们分成两部分,分别以蓝色和红色着色,而满足毕达哥拉斯著名方程 a^2 + b^2 = c^2的数a,b和c不能是同一种颜色。举例来说,对于勾股数3,4,5,如果3和5是蓝色,那么4必须是红色。在计算机的帮助下,研究人员证明,集合N={1,2,...7824} 能满足条件,但到7825时就不可能保证每一个毕达哥拉斯三元数颜色不同。{1,2,...7825} 有10^2300种着色方法,研究人员利用对称性和数论技术设法将计算机需要检查的可能着色方法减少到1万亿以内,然后利用Stampede的800个核心运行了2天。7825这个数有什么特别意义,计算机无法给出解释。

评论已经自动封存,请勿再发言论
显示选项 样式:
声明: 下面的评论属于其发表者所有,不代表本站的观点和立场,我们不负责他们说什么。
  • 7825有什么意义不好说(得分:1 )

    rahj(32935) Neutral 发表于2016年05月31日 16时23分 星期二
    但是7824=163*48 163的意义就不说了,48是个什么玩意
    为啥不是49或者42
    • 3天48小时? 匿名用户 (得分:0) 2016年05月31日 17时31分 星期二

    • 48 = 16 * 3,163?? 匿名用户 (得分:0) 2016年06月01日 16时32分 星期三

      • re:48 = 16 * 3,163??(得分:1 )

        rahj(32935) Neutral 发表于2016年06月03日 08时45分 星期五
        163都不知道?数论里头的一个很奇怪的数,与群论也有联系
        具体查找多项式x2+x+41=0
      • f(x)=12x^2+x-163(得分:1 )

        rahj(32935) Neutral 发表于2016年06月03日 08时49分 星期五
        大致如此,你算下exp^(pi*sqr(163))
  • 来自 答案是42 部门(得分:1 )

    lot(21642) Neutral 发表于2016年05月31日 16时39分 星期二
    至于终极问题是什么, 你们人类去想.
  • 答案不是42,不幸福(得分:1 )

    wudimajia(28478) Neutral 发表于2016年05月31日 19时20分 星期二
    如题
  • 就算人類證明出來,那內容可能也不是人人都能讀的懂,也未必會有什麼解釋。(得分:1 )

    Likey(30119) Neutral 发表于2016年06月01日 09时19分 星期三
    就算人類證明出來,那內容可能也不是人人都能讀的懂,也未必會有什麼解釋。
  • 楼上都找错了重点。(得分:1 识见广博)

    匿名用户 发表于2016年06月03日 15时14分 星期五
    重点是不是7824这个数,而是7825。
    这个问题在于,7825这个数所联系起来的三数组的图,其连接形式造成任意染色方法一定会产生同色组。
    每加入一个新的数字,就可能会多出一些三数组。然后加入7825这个数字的时候,形成的新图达到了“不管怎样染色都会有某个三数组同色”的要求。
    那么,加入7825这个数,增加了哪些三数组?
    简单算一下,得到了625 7800, 1584 7663, 2191 7512, 2784 7313, 4180 6615, 4695 6260, 5180 5865,
    7组。换句话说,在加入7825之前的所有合法染色方法,这些数字里至少有一对同时为红色,而至少还有一对同时为蓝色,所以新加入了7825后就无法继续染色。
    而加入7824这个数字增加了多少三数组呢?……是0个,也就是这个数字没有任何贡献。所以你们讨论这个数字有个毛意义啊……
    当然7824也是存在于三数组中的——但是是作为短边。实际上,除了1和2,其他任何数字都可以作为三数组中的短边。只不过在这个问题里没有任何意义,因为用到它时必须得带上长边,所以新加入的数字必须作为长边才有意义。
    我又想看一下,是不是增加7个三数组是最高的增加数?结果跑了一下,发现并不算高,增加数最高的是5525,增加22个组合。
    具体分布如下 [0] 2830, [1] 3616, [2] 222, [3] 41, [4] 943, [5] 2, [6] 0, [7] 116, [8] 0, [9] 0, [10] 13, [11] 0, [12] 2, [13] 40, [14] 0, [15] 0, [16] 0, [17] 0, [18] 0, [19] 0, [20] 0, [21] 0, [22] 1
    有点奇怪的,没什么规律的分布。很有意思,有空可以研究一下。

    不过话说回来,至于原问题,通过穷举法找到一个反例,这有什么需要解释的?虽然我也很好奇造成矛盾的图到底是什么,不过可能有几百个三角形纠结在一起,估计最简化后也有几十个,也没法直观理解吧。
    • re:楼上都找错了重点。(得分:1 )

      illusiwind(11967) Neutral 发表于2016年06月03日 15时15分 星期五
      ……为什么点了提交就变成匿名了嘛。
      --
      上帝死了,虽然不是我杀的。但是如果祂还活着,我一定会——再杀一次。