解決了凱勒猜想的計算機科學家劍指3x+1問題

2020-09-03 本人楊建東

Marijn Heule在過去的幾年中取得了輝煌戰功。他應用被稱為SAT solving (SAT表示「可滿足性」，不是美國高考那個縮寫)的計算機證明技術，徵服了一系列令人印象深刻的數學問題：2016年的勾股三元數問題，2017年的舒爾數=5時的舒爾猜想，以及現在為凱勒猜想畫上句號。

關於凱勒猜想，可見前文90年歷史的凱勒猜想被數學家利用計算機解決

但是，卡內基梅隆大學的計算機科學家Heule擁有更大的雄心：Collat​​z猜想，它被許多人認為是數學中最臭名昭著的開放問題(也是最容易被表述的問題)。

考拉茲猜想Collatz conjecture，俗稱3x+1猜想，大概是著名數學中表述最為簡單的一個。但是，曾有知名數學家告誡年輕學者：不要碰考拉茲猜想！不要被命題那人畜無害的外表所蒙蔽，那是惡魔設下的陷阱啊！

所謂的考拉茲猜想，就是大名鼎鼎的3x+1猜想。具體的內容是說，任取一個自然數x，如果x是偶數，則除以2；反之，3x+1後，再除以2；如此得到的數字記為x1，對x1繼續執行如上的操作得到x2……如此反覆，最終必然能夠得到數字1！

整套運算都沒有脫離加減乘除的範圍。

匹茲堡大學計算機證明領域的負責人Thomas Hales說：「我看不出如何使用SAT solving解決它。」不過與其他人一樣，Hales僅謹慎地表示不樂觀。「他非常擅長尋找將問題編碼為SAT的巧妙方法。他在這方面確實出色。」

德克薩斯大學奧斯汀分校，正在與Heule合作攻堅Collat​​z猜想的Scott Aaronson補充說：「Marijn手裡有一個錘子，那就是SAT solving——可能是世界上最偉大的一把錘子。所以他期望所有問題都能變成釘子。」時間會證明他是否可以將Collat​​z變成釘子。

至於說什麼是SAT solving，簡單來說：將問題轉化為使用命題邏輯的計算機語句，並使用計算機確定是否有辦法使這些語句的真值=1。

小紅，小黃，小綠，小藍四個人分別穿著紅黃綠藍四種顏色的衣服和紅黃綠藍四種顏色的褲子。已知條件如下：

1 只有1個人的名字與自己衣服的顏色相同；

2 只有1個人的名字與自己褲子的顏色相同；

3 沒有1個人的名字與自己的衣服和褲子的顏色完全相同；

4 穿紅衣服的人(不是小藍)的名字與小藍穿的褲子顏色相同；

5 穿藍衣服的人(不是小黃)的名字與小黃穿的褲子顏色相同。

請問四人分別穿什麼顏色的衣服和褲子？

一種檢索方法是將人名和顏色約束條件轉換為公式，然後輸入SAT解算器。該程序將找出是否有辦法(一般是循環為各個變量賦值0或1)使公式輸出結果為true或「令人滿意」。

不幸的是，數學中許多最重要的問題乍看之下和SAT問題毫無關係。但是有時可以用令人驚訝的方式將它們重新表述為可滿足性問題。

為了將Collat​​z猜想轉化成SAT問題，Aaronson和Heule必須採取進一步的措施。它涉及矩陣，他們將符號轉換視為矩陣乘法。

卡內基·梅隆大學的研究生Emre Yolcu說：「您試圖找到滿足這些約束的矩陣。如果找到它們，就嘗試證明他們的乘機不會越來越大。」亦即相當於證明了Collat​​z猜想。

「是否存在滿足這些約束的矩陣？」是適用於SAT solving的一類問題。Aaronson和Heule在小型2×2矩陣上啟動了SAT解算器。毫無效果。接下來，他們嘗試了3×3矩陣。運氣還是不佳。Heule和Aaronson不斷增加矩陣的大小，希望能找到合適的矩陣。

但是，隨著矩陣規模的增大，搜索正確矩陣的複雜性呈指數增長。Heule估計，任何大於12x12的矩陣都會噎死當今的計算機。

Heule仍在努力優化搜索，試圖提高搜索效率。

畢竟，SAT solving的誘人之處在於，您只要構思出正確的算法，再有點耐心，便會得到想要的東西。在這方面，Heule最重要的資產可能不是他應用SAT solving的技術，而是他對真理和數學的熱情。

他說：「我是樂觀的人。我經常感到運氣在自己這邊，所以我想嘗試一下，看看能走多遠。」

相關焦點

  • 困擾數學家90年的猜想,被計算機搜索30分鐘解決了
    1940年，數學家Perron證明了凱勒猜想在1到6維空間是正確的。 1992年，另外兩位數學家Lagarias和Shor證明，凱勒猜想在10維空間上是錯誤的。 （註：這位Shor就是那個提出用量子計算機求解質因數分解的Shor算法的數學家。）
  • 陶哲軒稍稍撬動了3x+1猜想
    菲爾茲獎得主、著名的華裔數學家陶哲軒在9月10日的博客上發表了關於考拉茲猜想Collatz conjecture部分結果的證明。 所謂的考拉茲猜想，就是大名鼎鼎的3x+1猜想。
  • 熱議:陶哲軒發布部分解決3x+1猜想的結果
    考蘭茲猜想，俗稱3x+1，說的是這樣一個猜想：對於一個初始的正整數，如果它是偶數我們就把它除以2，如果是奇數就把這個數乘以3再加上1。這樣將得到一個新的數字，再把這個新得到的數做之前重複的操作——如果它是偶數我們就把它除以2，如果是奇數就把這個數乘以3再加上1，然後又繼續得到一個數。
  • 介紹3x+1猜想的「弟弟」猜想——有趣的x+1遊戲,快和孩子玩一玩
    數學上有一個至今未解的難題就是「3x+1」猜想。其內容是這樣的：任取一個正整數，如果它是偶數，我們就把它除以2，如果它是奇數，我們就把它乘3再加上1。在這樣一個變換下，我們就得到了一個新的正整數。比如說，我們取一個自然數3，它是奇數，所以我們計算3x+1=3×3+1=10，得到了10；10是偶數，所以我們計算10÷2=5，得到了5；5是奇數，我們就計算3x+1=3×5+1=16；16是偶數，所以計算16÷2=8，得到了8；8是偶數，計算8÷2=4，得到了4；4是偶數，計算4÷2=2，得到了2；2是偶數，計算2÷2=1，得到了1；1是奇數，
  • 作家張溢稱以論證哥德巴赫猜想1+1與3x+1獲獎的唐國明為月上書生
    恭喜您的作品《這樣論證哥德巴赫猜想1+1與3x+1》在本次大賽中獲得入圍獎。……獲獎了，獲得入圍獎也是我覺得高興的事，也許大家更好奇我這篇獲獎小說提到哥德巴赫猜想1+1與世界數學難題3x+1猜想的內容，其實者這篇小說就是我以小說形式寫我論證了哥德巴赫猜想1+1與世界數學難題3x+1猜想得出了自己結論的自傳，自2017年3月31日後尤其關於哥德巴赫猜想1+1與世界數學難題3x+1猜想論證的論文發布網上後引起了不少關注與討論
  • 終於,科學家們找到了只有量子計算機才能解決的問題
    而在今年 5 月發表的一篇論文中，計算機科學家 Ran Raz（普林斯頓大學兼魏茨曼科學研究院教授） 和 Avishay Tal（史丹福大學博士後研究員）為「量子計算在能力上將遠超一切傳統計算」這一概念提供了科學證據。1993 年時，計算機學家將那些傳統計算望塵莫及，只有量子級計算才能解決的問題定義為 BQP 問題。
  • 2018年數學與計算機大事件:18歲少年大放異彩!ABC猜想
    量子霸權的延遲甚至導致一些理論計算機科學家認為，量子計算機永遠不會超越最好的經典計算機。理論上，任何職業數學家都應該能夠分辨出來，一個數學證明要麼是正確的，要麼就還需要更多補充。但在實踐中，一個看上去合乎邏輯的數學問題證明也能難道不少數學家。其中最典型的例子便是ABC猜想。ABC猜想是數論中的一個重要問題。
  • 困擾計算機圈近三十年的布爾函數敏感度猜想,華人數學家解決了
    這成為了理論計算機科學近三十年來最重要的開放性問題之一。近日，來自Emory大學計算機與數學科學系的華人教授黃皓，用兩頁紙輕鬆證明了困擾理論計算機領域數十年的問題。 組成計算機的電路實際上是「與」「或」「非」邏輯電路的組合，多年來，計算機科學家已經開發出許多方法來測量給定布爾函數的複雜性。
  • 2018年數學與計算機大事件:18歲少年大放異彩!ABC猜想證明被推翻?
    量子霸權的延遲甚至導致一些理論計算機科學家認為，量子計算機永遠不會超越最好的經典計算機。理論上，任何職業數學家都應該能夠分辨出來，一個數學證明要麼是正確的，要麼就還需要更多補充。但在實踐中，一個看上去合乎邏輯的數學問題證明也能難道不少數學家。其中最典型的例子便是ABC猜想。ABC猜想是數論中的一個重要問題。
  • 量子計算機、康威扭結、奧數AI,這是2020年計算機、數學重大突破
    當然，兩名數學家疫情隔離期間，破解陶哲軒挑戰失敗的百年數學問題，也榜上有名。一起來看看。TOP1：「量子糾纏」重大突破今年，計算機領域最重要的突破，是MIP*=RE的證明。它的證明，意味著利用量子邏輯來計算的量子計算機（而非利用0和1進行計算的經典計算機），可以從理論上驗證大量問題的答案。
  • 量子計算機、康威扭結、奧數AI,這是2020年計算機、數學的重大突破
    TOP1：「量子糾纏」重大突破今年，計算機領域最重要的突破，是MIP*=RE的證明。它的證明，意味著利用量子邏輯來計算的量子計算機（而非利用0和1進行計算的經典計算機），可以從理論上驗證大量問題的答案。來自雪梨科技大學、加州理工學院、德克薩斯大學奧斯汀分校、和多倫多大學的五位計算機科學家，將研究成果聯名發表在了一篇叫做《MIP * = RE》的論文上。
  • 三種證明考拉茲猜想的簡要說明
    海天出版社最近出版的基礎數學論文專輯《數學底層引擎相鄰論和重合法》一書，作者羅莫嘗試證明了30多個久未解決的數論猜想，其中就有考拉茲猜想，該猜想自從去年引起陶哲軒的注意後，一度在網絡上很火，多位數學愛好者聲稱完成了證明。
  • 讀研被導師安排了計算機領域最難的問題,還解出來了是什麼體驗?
    但這就是Nathan Klein兩年前遇到的事，他的導師邀請他一起解決的問題是旅行商問題，是理論計算機科學家試圖解決的基礎性問題之一，旨在探索高效計算（efficient computation）的極限。即使無法解決該問題，他們認為Klein也會在這個過程中學到很多東西。
  • 生活離不開猜想,從角谷猜想說起,期待你的挑戰
    生活離不開猜想，解決數學問題需要猜想，科學研究建立在猜想之上……,猜想，繞不過的彎。好的猜想猶如引路石，引導我們向前，從猜想走向發現。著名物理學家牛頓說：「沒有大膽的猜想，就做不出偉大的發現。」當代著名科學哲學家波普爾說：「我們的科學知識，是利用未經證明的和不可證明的預言，進行猜測，通過對問題的嘗試性解決，最終猜想而進步的.」觀察、實驗、猜想是科學研究的重要方法，通過觀察和實驗提出問題，再進行猜想和假設，最後通過推理去證明猜想和假設。
  • 哥德巴赫猜想不是證明1+1=2!數學皇冠上的明珠究竟是什麼?
    介紹之前，小編要事先說明，哥德巴赫猜想不是要證明1+1=2，大夥平時討論這個問題時千萬不要瞎說哥德巴赫猜想是證明1+1=2。這樣說真的是太無知太雷人了，現在就連一些中小學的數學老師都會有這種錯誤認知，這真的是誤人子弟。
  • 考拉茲猜想獲得完全證明:冪尾數周期律與質函數迭代律
    而本文作者給出的證明，妙在找到了如何歸簡的思路，同證明費馬猜想一樣，然後通過排除無法歸簡的族集，從而得到命題的精準證明。該證明方法與證明希爾伯特第八問題的思路也是一致的。先找到至簡和至繁的各自等式，然後找到至繁與至簡之間的貫穿階梯，既要找到交集和全集各自的等價變換，又要找到交集到全集，全集到交集的梯級變換。概念逐級打通，問題自然解決。
  • 藉助計算機解決數學難題其實可以很有趣
    目前，許多科學家正在藉助計算機來解決數學難題，相信不久的將來這方面將會有所突破。尤其是運算量極其龐大的數學問題，大多數情況只能藉助計算機來解決。例如，四色問題、E8結構、費克特問題、克卜勒猜想、埃爾德什差異問題、畢氏三元數問題、x^3+y^3+z^3=k方程等著名數學難題，都是藉助計算機來破解的。從上世紀50年代中期起，數學家開始用計算機進行證明定理的嘗試。
  • 圓周率已被算到31.4萬億位,科學家猜想:圓周率終點是宇宙奇點?
    現代科技的迅猛發展，已經讓人類窺探到了更多的「真理」，尤其是超級計算機的發明，更是讓人類的計算能力達到一個非常恐怖的地步，也許你們還不知道，目前人類已經將圓周率給算到31.4萬億位，並且甚至有科學家提出猜想：圓周率終點是宇宙奇點？
  • 小樂數學科普:攻克3n+1猜想你所需要掌握的知識第一季第1集
    小樂導讀：3n+1猜想是至今（2020-11-24）仍未被解決的數學難題之一，它斷言任何一個正整數經過一種函數f(x)反覆迭代之後，最終會得到1，無一例外。而函數f(x)規則很簡單，當x是偶數時，f(x)=x/2；當x是奇數時，f(x)=3x+1，由於規則如此簡單，上世紀這個猜想曾經在美國風靡一時（但都無果），而如今它也已經在中國初一數學習題中反覆出現（小學生也應能看懂）。從本期開始，小樂將陸續整理已知公開的權威公認資料，按季發布，方便學者追蹤此問題，直至此問題被徹底解決。