建站
咨詢
售后
建站咨詢
新聞中心
本文經(jīng)AI新媒體量子位（公眾號(hào)ID:QbitAI）授權(quán)轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)聯(lián)系出處。
創(chuàng)新互聯(lián)是一家以網(wǎng)絡(luò)技術(shù)公司，為中小企業(yè)提供網(wǎng)站維護(hù)、成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司、網(wǎng)站備案、服務(wù)器租用、域名注冊(cè)、軟件開(kāi)發(fā)、成都小程序開(kāi)發(fā)等企業(yè)互聯(lián)網(wǎng)相關(guān)業(yè)務(wù)，是一家有著豐富的互聯(lián)網(wǎng)運(yùn)營(yíng)推廣經(jīng)驗(yàn)的科技公司，有著多年的網(wǎng)站建站經(jīng)驗(yàn)，致力于幫助中小企業(yè)在互聯(lián)網(wǎng)讓打出自已的品牌和口碑，讓企業(yè)在互聯(lián)網(wǎng)上打開(kāi)一個(gè)面向全國(guó)乃至全球的業(yè)務(wù)窗口：建站歡迎咨詢：028-86922220
數(shù)學(xué)家會(huì)代碼，誰(shuí)也擋不住！就連困擾人類90年的數(shù)學(xué)猜想也擋不住。
來(lái)自斯坦福、CMU等高校的4名數(shù)學(xué)家，將一個(gè)數(shù)學(xué)難題轉(zhuǎn)化成了對(duì)10億個(gè)結(jié)果進(jìn)行“暴力搜索”。
△ 論文作者之一CMU助理教授Marijn Heule
他們把這串代碼輸入40臺(tái)電腦組成的計(jì)算集群，30分鐘后，計(jì)算機(jī)給出了一個(gè)200GB大小的證明結(jié)果：
凱勒猜想在不超過(guò)7維的空間上都是正確的。
現(xiàn)在，任何人都可以去GitHub上克隆這串代碼，驗(yàn)證這一數(shù)學(xué)定理。
比較反轉(zhuǎn)的是，這段獲得計(jì)算機(jī)學(xué)術(shù)會(huì)議IJCAR（國(guó)際自動(dòng)推理聯(lián)合會(huì)議）最佳論文獎(jiǎng)的程序，上線GitHub半年，只攬獲了一顆星。
那么，這4位數(shù)學(xué)家要證明的“凱勒猜想”到底是什么？為何非要用計(jì)算機(jī)來(lái)證明？計(jì)算機(jī)證明的結(jié)果可靠嗎？
下面讓我們一一道來(lái)。
什么是凱勒猜想
假如用一批完全相同的正方形瓷磚鋪滿地面，中間不留空隙。顯然，瓷磚之間會(huì)共用一條邊，如下圖藍(lán)線所示：
在3維空間中，如果要用立方體占滿空間，是不是也和2維空間類似呢？
想象一下，如果像下圖那樣在空間中隨便放入幾個(gè)立方體，由此展開(kāi)填滿整個(gè)空間，那么唯一的辦法就是讓接上的立方體共用藍(lán)色的面。
2維、3維皆如此，更高維度的空間會(huì)怎樣？
1930年，德國(guó)數(shù)學(xué)家凱勒猜測(cè)，如果用n維立方體填滿無(wú)限空間，則立方體之間必然會(huì)出現(xiàn)“面對(duì)面”，對(duì)于任意維度都成立。
這便是凱勒猜想。
但數(shù)學(xué)猜想不能僅靠直覺(jué)，必須有嚴(yán)格的證明。90年來(lái)，數(shù)學(xué)家一直不懈努力。
1940年，數(shù)學(xué)家Perron證明了凱勒猜想在1到6維空間是正確的。
1992年，另外兩位數(shù)學(xué)家Lagarias和Shor證明，凱勒猜想在10維空間上是錯(cuò)誤的。
（注：這位Shor就是那個(gè)提出用量子計(jì)算機(jī)求解質(zhì)因數(shù)分解的Shor算法的數(shù)學(xué)家。）
非常不幸，凱勒猜想竟然是錯(cuò)的！然而問(wèn)題并沒(méi)有到此結(jié)束。
還有3個(gè)維度沒(méi)有解決呢！在7維、8維、9維三個(gè)維度空間中，凱勒猜想是否成立？
只要解決這三個(gè)維度，纏繞數(shù)學(xué)家?guī)资甑膯?wèn)題就徹底搞定了。
數(shù)學(xué)論證表明，如果凱勒猜想在n維空間上是錯(cuò)的，那么它在比n更高的維度上也一定是錯(cuò)的。
2002年，數(shù)學(xué)家Mackey已證明，凱勒猜想在8維空間不成立，因此在9維空間也不成立。
至此，7維空間成為唯一的難題。
△ 證明8維空間凱勒猜想錯(cuò)誤的CMU教授Mackey
證明方法的改進(jìn)
可能你已經(jīng)發(fā)現(xiàn)，從上世紀(jì)90年代以來(lái)，凱勒猜想的證明速度大大加快，數(shù)學(xué)家只用了10年時(shí)間就把問(wèn)題縮小到三個(gè)維度。
這主要得益于兩位數(shù)學(xué)家的貢獻(xiàn)。
當(dāng)年，Perron求解1到6維時(shí)，沒(méi)有特殊的捷徑。而到1990年，凱勒猜想的證明方法發(fā)生了巨大的變化。
數(shù)學(xué)家Corrádi和Szabó提出了一種新的思路，把原來(lái)無(wú)限空間的問(wèn)題變成有限的、離散的問(wèn)題，也讓計(jì)算機(jī)解決凱勒猜想成為可能。
他們巧妙地把凱勒猜想變成了圖論問(wèn)題，就是構(gòu)造所謂的凱勒?qǐng)D（Keller Graph），而圖論正是計(jì)算機(jī)所擅長(zhǎng)的。
在這種方法的指導(dǎo)下，Lagarias和Shor兩人很快在2年后就證明了10維空間的情況：凱勒猜想不成立。又過(guò)了10年，Mackey證明，凱勒猜想在8維空間不成立。
那么，凱勒?qǐng)D究竟是什么，它為什么能夠加速凱勒猜想的證明？
構(gòu)造“凱勒?qǐng)D”
首先，我們從最簡(jiǎn)單的2維情況說(shuō)起。
現(xiàn)在，我們有一種牌，牌上畫(huà)著兩個(gè)有顏色的點(diǎn)。兩個(gè)點(diǎn)是有順序的，不能調(diào)換。比如，1黑2白≠1白2黑。
兩個(gè)點(diǎn)總共可以涂4種顏色，顏色分成2對(duì)：紅色對(duì)綠色、白色對(duì)黑色。
數(shù)學(xué)家已經(jīng)證明，分配給點(diǎn)的顏色相當(dāng)于正方形在空間中的坐標(biāo)。兩張牌的顏色是否配對(duì)表示兩個(gè)正方形的相對(duì)位置。
點(diǎn)的顏色與正方形的具體關(guān)系是這樣的：
1、兩對(duì)點(diǎn)完全相同，表示兩個(gè)正方形完全重疊
2、兩對(duì)點(diǎn)顏色都不同，且顏色都不配對(duì)，表示兩個(gè)正方形有部分重疊
3、一對(duì)點(diǎn)顏色相同，另一對(duì)點(diǎn)顏色配對(duì)，表示兩個(gè)正方形共用一個(gè)邊
4、一對(duì)點(diǎn)顏色不同，另一對(duì)點(diǎn)顏色配對(duì)，表示兩個(gè)正方形的邊相互接觸但不重合
2個(gè)點(diǎn)的凱勒?qǐng)D，要用2對(duì)顏色去填充牌面，總共有16種情況。
然后我們把這16張牌擺在桌上，只有符合前面條件4的兩張牌，才用線將二者連起來(lái)。這樣就構(gòu)成了一張“凱勒?qǐng)D”。
包含16張牌的凱勒?qǐng)D就描繪了正方形填補(bǔ)平面的所有可能。
如果2維空間中凱勒猜想不成立，那么我們肯定能找到4個(gè)正方形，它們之間沒(méi)有共用的邊，但是能夠無(wú)縫隙填在一起。然后在屏幕上無(wú)限復(fù)制這4個(gè)正方形，就能填滿整個(gè)屏幕。
實(shí)際上并不可能。如果按此操作，只會(huì)得到有著無(wú)數(shù)孔隙（下圖紫色部分）的填充方式。
對(duì)應(yīng)到凱勒?qǐng)D中，就是找在圖中找到4張牌，它們兩兩之間都有連線。（在數(shù)學(xué)里，這叫做完全圖。）
顯然，在2維問(wèn)題的凱勒?qǐng)D中，我們找不到這樣的4張牌。（可以自己去上面的凱勒?qǐng)D中找找看。）
這樣，我們把就把n維立方體以及位移s與牌的點(diǎn)數(shù)n、顏色對(duì)數(shù)s聯(lián)系起來(lái)。
作為更一般的規(guī)則，如果要證明n維凱勒猜想是錯(cuò)的，就要在對(duì)應(yīng)的凱勒?qǐng)D中找到2n張牌，且這些牌兩兩相連。
正因?yàn)槟阏也坏?個(gè)張牌組成的完全圖，所以2維空間的凱勒猜想是對(duì)的。
為了在3維空間中證明凱勒猜想，可以使用216張牌，每張牌上3個(gè)點(diǎn)，并可以使用3對(duì)顏色（這一點(diǎn)相對(duì)靈活）。然后，我們需要尋找23=8張牌 ，它們兩兩之間都有連線，但還是找不到。
到了8維空間中，我們總算可以找到符合條件的256張牌，所以8維空間的凱勒猜想是錯(cuò)的。
△8維空間中的一個(gè)反例（一個(gè)凱勒?qǐng)D的完全子圖）
接下來(lái)的事情就是在7維空間對(duì)應(yīng)的凱勒?qǐng)D上尋找完全子圖。然而這個(gè)問(wèn)題卻從8維問(wèn)題解決后被擱置了17年。
根據(jù)前面的說(shuō)明，求解8維空間和10維空間的凱勒猜想，要尋找28=256和210=1024張牌的子圖，而7維空間只要尋找27=128張牌的子圖。
后者的難度似乎更小，7維空間的問(wèn)題應(yīng)該更簡(jiǎn)單??！其實(shí)不然。
因?yàn)?，從某種意義上說(shuō)，8維和10維可以“分解”為容易計(jì)算的較低維度，但7維不行。
證明了10維情況的Lagarias說(shuō)：“7維不好，因?yàn)樗琴|(zhì)數(shù)，這意味著你無(wú)法將其分解為低維。因此別無(wú)選擇，只能處理這些圖的全部組合?！?/p>
對(duì)于人腦來(lái)說(shuō)，尋找大小為128的子圖是一項(xiàng)艱巨的任務(wù)，但這恰恰是計(jì)算機(jī)擅長(zhǎng)回答的問(wèn)題。
計(jì)算機(jī)幫忙
說(shuō)干就干，此前證明8維問(wèn)題的CMU教授Mackey拉上了斯坦福的數(shù)學(xué)在讀博士Brakensiek和專長(zhǎng)計(jì)算機(jī)輔助證明的助理教授Heule。
回憶起立項(xiàng)的那天，Mackey說(shuō)，Brakensiek是真正的天才，看著他就像看著NBA總決賽里的詹姆斯。Brakensiek本人確實(shí)很厲害，他曾是2013/14兩屆國(guó)際信息學(xué)奧賽金牌得主。
△ 論文第一作者Brakensiek
言歸正傳。為了方便計(jì)算機(jī)求解，他們換了個(gè)方向來(lái)思考：
先設(shè)定牌上有7個(gè)點(diǎn)、6種可能的顏色，按照前面的“條件4”對(duì)這些牌上色，看看能不能找到128種不同的填色方法。如果找不到，那么凱勒猜想成立。
用計(jì)算機(jī)輔助證明數(shù)學(xué)問(wèn)題，還需要把它變成一系列邏輯運(yùn)算，也就是處理01之間的與或非關(guān)系。
若要求解7維，則總共包含39000個(gè)不同布爾變量（0或1），有239000種可能性，這是一個(gè)非常非常大的數(shù)字，有11741位數(shù)。
△2的39000次方（來(lái)自Wolfram Alpha運(yùn)算結(jié)果）
一臺(tái)普通電腦只能處理324位數(shù)種可能，離解決問(wèn)題還遠(yuǎn)得很。就算交給超級(jí)計(jì)算機(jī)也不夠。
但是，這幾位數(shù)學(xué)家想到了排除法，只要得到結(jié)論，而不必實(shí)際檢查所有可能性。效率才是王道！
比如，用計(jì)算機(jī)規(guī)則給128張牌上色，當(dāng)你涂到第12張牌的時(shí)候，發(fā)現(xiàn)找不到符合條件的下一張牌了。那么所有包含這12張牌的排列都可以排除。
提升效率的另一種方式是利用對(duì)稱性。如果已經(jīng)驗(yàn)證了某種排列不可能，那與之對(duì)稱的所有情況都可以排除。
通過(guò)這兩種方法，他們把搜索空間縮小到10億（230）。這樣一來(lái)，用計(jì)算機(jī)搜索變成了可能。
最終，他們僅計(jì)算了半個(gè)小時(shí)，便有了答案。
計(jì)算機(jī)沒(méi)有找到符合條件的128張牌，所以7維空間的凱勒猜想確實(shí)成立。
實(shí)際上，計(jì)算機(jī)提供的不僅僅是一個(gè)答案，證明的內(nèi)容多達(dá)200GB。4位論文作者將證明送入計(jì)算機(jī)的證明檢查器，確認(rèn)了它的可靠性。
解決了凱勒猜想后，Heule的下一個(gè)目標(biāo)是用計(jì)算機(jī)證明數(shù)學(xué)里“最簡(jiǎn)單的不可能問(wèn)題”——3n+1猜想，去年陶哲軒已經(jīng)“幾乎”解決了這個(gè)問(wèn)題，現(xiàn)在可能只差一步之遙了。
標(biāo)題名稱：困擾數(shù)學(xué)家90年的猜想，被計(jì)算機(jī)搜索30分鐘解決了
網(wǎng)站路徑：http://m.5511xx.com/article/cdiccdi.html
