一、P(多項(xiàng)式時(shí)間)問(wèn)題對(duì)NP(非確定多項(xiàng)式時(shí)間)問(wèn)題 在一個(gè)周六的晚上,你參加了一個(gè)盛大的晚會(huì)。由于感到局促不安,你想知道這一大廳中是否有你已經(jīng)認(rèn)識(shí)的人。你的主人向你提議說(shuō),你一定認(rèn)識(shí)那位正在甜點(diǎn)盤(pán)附近角落的女士羅絲。不費(fèi)一秒鐘,你就能向那里掃視,并且發(fā)現(xiàn)你的主人是正確的。然而,如果沒(méi)有這樣的暗示,你就必須環(huán)顧整個(gè)大廳,一個(gè)個(gè)地審視每一個(gè)人,看是否有你認(rèn)識(shí)的人。生成問(wèn)題的一個(gè)解通常比驗(yàn)證一個(gè)給定的解時(shí)間花費(fèi)要多得多。這是這種一般現(xiàn)象的一個(gè)例子。與此類(lèi)似的是,如果某人告訴你,數(shù)13717421可以寫(xiě)成兩個(gè)較小的數(shù)的乘積,你可能不知道是否應(yīng)該相信他,但是如果他告訴你它可以因式分解為3607乘上3803,那么你就可以用一個(gè)袖珍計(jì)算器容易驗(yàn)證這是對(duì)的。不管我們編寫(xiě)程序是否靈巧,判定一個(gè)答案是可以很快利用內(nèi)部知識(shí)來(lái)驗(yàn)證,還是沒(méi)有這樣的提示而需要花費(fèi)大量時(shí)間來(lái)求解,被看作邏輯和計(jì)算機(jī)科學(xué)中最突出的問(wèn)題之一。它是斯蒂文·考克于1971年陳述的。 二、霍奇猜想 三、龐加萊猜想 四、黎曼假設(shè) 五、楊-米爾斯存在性和質(zhì)量缺口 六、納維葉-斯托克斯方程的存在性與光滑性 七、貝赫和斯維訥通-戴爾猜想 1、費(fèi)爾馬大定理 1637年,法國(guó)業(yè)余大數(shù)學(xué)家費(fèi)爾馬(Pierre de Fremat)在“算術(shù)”的關(guān)于勾股數(shù)問(wèn)題的頁(yè)邊上,寫(xiě)下猜想:x^n+ y^n =z^n 是不可能的(這里n大于2;x,y,z,n都是非零整數(shù))。此猜想后來(lái)就稱(chēng)為費(fèi)爾馬大定理。費(fèi)爾馬還寫(xiě)道“我對(duì)此有絕妙的證明,但此頁(yè)邊太窄寫(xiě)不下”。一般公認(rèn),他當(dāng)時(shí)不可能有正確的證明。猜想提出后,經(jīng)歐拉等數(shù)代天才努力,200年間只解決了n=3,4,5,7四種情形。1847年,庫(kù)木爾創(chuàng)立“代數(shù)數(shù)論”這一現(xiàn)代重要學(xué)科,對(duì)許多n(例如100以?xún)?nèi))證明了費(fèi)爾馬大定理,是一次大飛躍。 歷史上費(fèi)爾馬大定理高潮迭起,傳奇不斷。其驚人的魅力,曾在最后時(shí)刻挽救自殺青年于不死。他就是德國(guó)的沃爾夫斯克勒,他后來(lái)為費(fèi)爾馬大定理設(shè)懸賞10萬(wàn)馬克(相當(dāng)于現(xiàn)在160萬(wàn)美元多),期限1908-2007年。無(wú)數(shù)人耗盡心力,空留浩嘆。最現(xiàn)代的電腦加數(shù)學(xué)技巧,驗(yàn)證了400萬(wàn)以?xún)?nèi)的N,但這對(duì)最終證明無(wú)濟(jì)于事。1983年德國(guó)的法爾廷斯證明了:對(duì)任一固定的n,最多只有有限多個(gè)x,y,z振動(dòng)了世界,獲得費(fèi)爾茲獎(jiǎng)(數(shù)學(xué)界最高獎(jiǎng))?! v史的新轉(zhuǎn)機(jī)發(fā)生在1986年夏,貝克萊·瑞波特證明了:費(fèi)爾馬大定理包含在“谷山豐—志村五朗猜想 ” 之中。童年就癡迷于此的懷爾斯,聞此立刻潛心于頂樓書(shū)房7年,曲折卓絕,匯集了20世紀(jì)數(shù)論所有的突破性成果。終于在1993年6月23日劍橋大學(xué)牛頓研究所的“世紀(jì)演講”最后,宣布證明了費(fèi)爾馬大定理。立刻震動(dòng)世界,普天同慶。不幸的是,數(shù)月后逐漸發(fā)現(xiàn)此證明有漏洞,一時(shí)更成世界焦點(diǎn)。這個(gè)證明體系是千萬(wàn)個(gè)深?yuàn)W數(shù)學(xué)推理連接成千個(gè)最現(xiàn)代的定理、事實(shí)和計(jì)算所組成的千百回轉(zhuǎn)的邏輯網(wǎng)絡(luò),任何一環(huán)節(jié)的問(wèn)題都會(huì)導(dǎo)致前功盡棄。懷爾斯絕境搏斗,毫無(wú)出路。1994年9月19日,星期一的早晨,懷爾斯在思維的閃電中突然找到了迷失的鑰匙:解答原來(lái)就在廢墟中!他熱淚奪眶而出。懷爾斯的歷史性長(zhǎng)文“模橢圓曲線和費(fèi)爾馬大定理”1995年5月發(fā)表在美國(guó)《數(shù)學(xué)年刊》第142卷,實(shí)際占滿(mǎn)了全卷,共五章,130頁(yè)。1997年6月27日,懷爾斯獲得沃爾夫斯克勒10萬(wàn)馬克懸賞大獎(jiǎng)。離截止期10年,圓了歷史的夢(mèng)。他還獲得沃爾夫獎(jiǎng)(1996.3),美國(guó)國(guó)家科學(xué)家院獎(jiǎng)(1996.6),費(fèi)爾茲特別獎(jiǎng)(1998.8)。 四色問(wèn)題的內(nèi)容是:“任何一張地圖只用四種顏色就能使具有共同邊界的國(guó)家著上不同的顏色?!庇脭?shù)學(xué)語(yǔ)言表示,即“將平面任意地細(xì)分為不相重疊的區(qū)域,每一個(gè)區(qū)域總可以用1,2,3,4這四個(gè)數(shù)字之一來(lái)標(biāo)記,而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字?!保ㄓ覉D) 這里所指的相鄰區(qū)域,是指有一整段邊界是公共的。如果兩個(gè)區(qū)域只相遇于一點(diǎn)或有限多點(diǎn),就不叫相鄰的。因?yàn)橛孟嗤念伾o它們著色不會(huì)引起混淆?! ∷纳孪氲奶岢鰜?lái)自英國(guó)。1852年,畢業(yè)于倫敦大學(xué)的弗南西斯·格思里來(lái)到一家科研單位搞地圖著色工作時(shí),發(fā)現(xiàn)了一種有趣的現(xiàn)象:“看來(lái),每幅地圖都可以用四種顏色著色,使得有共同邊界的國(guó)家都被著上不同的顏色?!边@個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢?他和在大學(xué)讀書(shū)的弟弟格里斯決心試一試。兄弟二人為證明這一問(wèn)題而使用的稿紙已經(jīng)堆了一大疊,可是研究工作沒(méi)有進(jìn)展。 1852年10月23日,他的弟弟就這個(gè)問(wèn)題的證明請(qǐng)教了他的老師、著名數(shù)學(xué)家德·摩爾根,摩爾根也沒(méi)有能找到解決這個(gè)問(wèn)題的途徑,于是寫(xiě)信向自己的好友、著名數(shù)學(xué)家漢密爾頓爵士請(qǐng)教。漢密爾頓接到摩爾根的信后,對(duì)四色問(wèn)題進(jìn)行論證。但直到1865年漢密爾頓逝世為止,問(wèn)題也沒(méi)有能夠解決?! ?872年,英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問(wèn)題,于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問(wèn)題。世界上許多一流的數(shù)學(xué)家都紛紛參加了四色猜想的大會(huì)戰(zhàn)。1878~1880年兩年間,著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文,宣布證明了四色定理,大家都認(rèn)為四色猜想從此也就解決了?! 】掀盏淖C明是這樣的:首先指出如果沒(méi)有一個(gè)國(guó)家包圍其他國(guó)家,或沒(méi)有三個(gè)以上的國(guó)家相遇于一點(diǎn),這種地圖就說(shuō)是“正規(guī)的”(左圖)。如為正規(guī)地圖,否則為非正規(guī)地圖(右圖)。一張地圖往往是由正規(guī)地圖和非正規(guī)地圖聯(lián)系在一起,但非正規(guī)地圖所需顏色種數(shù)一般不超過(guò)正規(guī)地圖所需的顏色,如果有一張需要五種顏色的地圖,那就是指它的正規(guī)地圖是五色的,要證明四色猜想成立,只要證明不存在一張正規(guī)五色地圖就足夠了?! 】掀帐怯?font color="#000000">歸謬法來(lái)證明的,大意是如果有一張正規(guī)的五色地圖,就會(huì)存在一張國(guó)數(shù)最少的“極小正規(guī)五色地圖”,如果極小正規(guī)五色地圖中有一個(gè)國(guó)家的鄰國(guó)數(shù)少于六個(gè),就會(huì)存在一張國(guó)數(shù)較少的正規(guī)地圖仍為五色的,這樣一來(lái)就不會(huì)有極小五色地圖的國(guó)數(shù),也就不存在正規(guī)五色地圖了。這樣肯普就認(rèn)為他已經(jīng)證明了“四色問(wèn)題”,但是后來(lái)人們發(fā)現(xiàn)他錯(cuò)了。 不過(guò)肯普的證明闡明了兩個(gè)重要的概念,對(duì)以后問(wèn)題的解決提供了途徑。第一個(gè)概念是“構(gòu)形”。他證明了在每一張正規(guī)地圖中至少有一國(guó)具有兩個(gè)、三個(gè)、四個(gè)或五個(gè)鄰國(guó),不存在每個(gè)國(guó)家都有六個(gè)或更多個(gè)鄰國(guó)的正規(guī)地圖,也就是說(shuō),由兩個(gè)鄰國(guó),三個(gè)鄰國(guó)、四個(gè)或五個(gè)鄰國(guó)組成的一組“構(gòu)形”是不可避免的,每張地圖至少含有這四種構(gòu)形中的一個(gè)?! 】掀仗岢龅牧硪粋€(gè)概念是“可約”性?!翱杉s”這個(gè)詞的使用是來(lái)自肯普的論證。他證明了只要五色地圖中有一國(guó)具有四個(gè)鄰國(guó),就會(huì)有國(guó)數(shù)減少的五色地圖。自從引入“構(gòu)形”,“可約”概念后,逐步發(fā)展了檢查構(gòu)形以決定是否可約的一些標(biāo)準(zhǔn)方法,能夠?qū)で罂杉s構(gòu)形的不可避免組,是證明“四色問(wèn)題”的重要依據(jù)。但要證明大的構(gòu)形可約,需要檢查大量的細(xì)節(jié),這是相當(dāng)復(fù)雜的?! ?1年后,即1890年,在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計(jì)算指出了肯普在證明上的漏洞。他指出肯普說(shuō)沒(méi)有極小五色地圖能有一國(guó)具有五個(gè)鄰國(guó)的理由有破綻。不久,泰勒的證明也被人們否定了。人們發(fā)現(xiàn)他們實(shí)際上證明了一個(gè)較弱的命題——五色定理。就是說(shuō)對(duì)地圖著色,用五種顏色就夠了。后來(lái),越來(lái)越多的數(shù)學(xué)家雖然對(duì)此絞盡腦汁,但一無(wú)所獲。于是,人們開(kāi)始認(rèn)識(shí)到,這個(gè)貌似容易的題目,其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題?! ∵M(jìn)入20世紀(jì)以來(lái),科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行。1913年,美國(guó)著名數(shù)學(xué)家、哈佛大學(xué)的伯克霍夫利用肯普的想法,結(jié)合自己新的設(shè)想;證明了某些大的構(gòu)形可約。后來(lái)美國(guó)數(shù)學(xué)家富蘭克林于1939年證明了22國(guó)以下的地圖都可以用四色著色。1950年,有人從22國(guó)推進(jìn)到35國(guó)。1960年,有人又證明了39國(guó)以下的地圖可以只用四種顏色著色;隨后又推進(jìn)到了50國(guó)??磥?lái)這種推進(jìn)仍然十分緩慢?! 「咚贁?shù)字計(jì)算機(jī)的發(fā)明,促使更多數(shù)學(xué)家對(duì)“四色問(wèn)題”的研究。從1936年就開(kāi)始研究四色猜想的???,公開(kāi)宣稱(chēng)四色猜想可用尋找可約圖形的不可避免組來(lái)證明。他的學(xué)生丟雷寫(xiě)了一個(gè)計(jì)算程序,海克不僅能用這程序產(chǎn)生的數(shù)據(jù)來(lái)證明構(gòu)形可約,而且描繪可約構(gòu)形的方法是從改造地圖成為數(shù)學(xué)上稱(chēng)為“對(duì)偶”形著手?! ∷衙總€(gè)國(guó)家的首都標(biāo)出來(lái),然后把相鄰國(guó)家的首都用一條越過(guò)邊界的鐵路連接起來(lái),除首都(稱(chēng)為頂點(diǎn))及鐵路(稱(chēng)為弧或邊)外,擦掉其他所有的線,剩下的稱(chēng)為原圖的對(duì)偶圖。到了六十年代后期,海克引進(jìn)一個(gè)類(lèi)似于在電網(wǎng)絡(luò)中移動(dòng)電荷的方法來(lái)求構(gòu)形的不可避免組。在海克的研究中第一次以頗不成熟的形式出現(xiàn)的“放電法”,這對(duì)以后關(guān)于不可避免組的研究是個(gè)關(guān)鍵,也是證明四色定理的中心要素?! ‰娮佑?jì)算機(jī)問(wèn)世以后,由于演算速度迅速提高,加之人機(jī)對(duì)話(huà)的出現(xiàn),大大加快了對(duì)四色猜想證明的進(jìn)程。美國(guó)伊利諾大學(xué)哈肯在1970年著手改進(jìn)“放電過(guò)程”,后與阿佩爾合作編制一個(gè)很好的程序。就在1976年6月,他們?cè)诿绹?guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上,用了1200個(gè)小時(shí),作了100億判斷,終于完成了四色定理的證明,轟動(dòng)了世界?! ∵@是一百多年來(lái)吸引許多數(shù)學(xué)家與數(shù)學(xué)愛(ài)好者的大事,當(dāng)兩位數(shù)學(xué)家將他們的研究成果發(fā)表的時(shí)候,當(dāng)?shù)氐泥]局在當(dāng)天發(fā)出的所有郵件上都加蓋了“四色足夠”的特制郵戳,以慶祝這一難題獲得解決?! 八纳珕?wèn)題”的被證明僅解決了一個(gè)歷時(shí)100多年的難題,而且成為數(shù)學(xué)史上一系列新思維的起點(diǎn)。在“四色問(wèn)題”的研究過(guò)程中,不少新的數(shù)學(xué)理論隨之產(chǎn)生,也發(fā)展了很多數(shù)學(xué)計(jì)算技巧。如將地圖的著色問(wèn)題化為圖論問(wèn)題,豐富了圖論的內(nèi)容。不僅如此,“四色問(wèn)題”在有效地設(shè)計(jì)航空班機(jī)日程表,設(shè)計(jì)計(jì)算機(jī)的編碼程序上都起到了推動(dòng)作用?! 〔贿^(guò)不少數(shù)學(xué)家并不滿(mǎn)足于計(jì)算機(jī)取得的成就,他們認(rèn)為應(yīng)該有一種簡(jiǎn)捷明快的書(shū)面證明方法。直到現(xiàn)在,仍由不少數(shù)學(xué)家和數(shù)學(xué)愛(ài)好者在尋找更簡(jiǎn)潔的證明方法。 史上和質(zhì)數(shù)有關(guān)的數(shù)學(xué)猜想中,最著名的當(dāng)然就是“哥德巴赫猜想”了?! ?742年6月7日,德國(guó)數(shù)學(xué)家哥德巴赫在寫(xiě)給著名數(shù)學(xué)家歐拉的一封信中,提出了兩個(gè)大膽的猜想: 一、任何不小于6的偶數(shù),都是兩個(gè)奇質(zhì)數(shù)之和; 二、任何不小于9的奇數(shù),都是三個(gè)奇質(zhì)數(shù)之和。 這就是數(shù)學(xué)史上著名的“哥德巴赫猜想”。顯然,第二個(gè)猜想是第一個(gè)猜想的推論。因此,只需在兩個(gè)猜想中證明一個(gè)就足夠了?! ⊥?月30日,歐拉在給哥德巴赫的回信中,明確表示他深信哥德巴赫的這兩個(gè)猜想都是正確的定理,但是歐拉當(dāng)時(shí)還無(wú)法給出證明。由于歐拉是當(dāng)時(shí)歐洲最偉大的數(shù)學(xué)家,他對(duì)哥德巴赫猜想的信心,影響到了整個(gè)歐洲乃至世界數(shù)學(xué)界。從那以后,許多數(shù)學(xué)家都躍躍欲試,甚至一生都致力于證明哥德巴赫猜想??墒侵钡?9世紀(jì)末,哥德巴赫猜想的證明也沒(méi)有任何進(jìn)展。證明哥德巴赫猜想的難度,遠(yuǎn)遠(yuǎn)超出了人們的想象。有的數(shù)學(xué)家把哥德巴赫猜想比喻為“數(shù)學(xué)王冠上的明珠”?! ∥覀儚?=3+3、8=3+5、10=5+5、……、100=3+97=11+89=17+83、……這些具體的例子中,可以看出哥德巴赫猜想都是成立的。有人甚至逐一驗(yàn)證了3300萬(wàn)以?xún)?nèi)的所有偶數(shù),竟然沒(méi)有一個(gè)不符合哥德巴赫猜想的。20世紀(jì),隨著計(jì)算機(jī)技術(shù)的發(fā)展,數(shù)學(xué)家們發(fā)現(xiàn)哥德巴赫猜想對(duì)于更大的數(shù)依然成立??墒亲匀粩?shù)是無(wú)限的,誰(shuí)知道會(huì)不會(huì)在某一個(gè)足夠大的偶數(shù)上,突然出現(xiàn)哥德巴赫猜想的反例呢?于是人們逐步改變了探究問(wèn)題的方式?! ?900年,20世紀(jì)最偉大的數(shù)學(xué)家希爾特,在國(guó)際數(shù)學(xué)會(huì)議上把“哥德巴赫猜想”列為23個(gè)數(shù)學(xué)難題之一。此后,20世紀(jì)的數(shù)學(xué)家們?cè)谑澜绶秶鷥?nèi)“聯(lián)手”進(jìn)攻“哥德巴赫猜想”堡壘,終于取得了輝煌的成果?! ?0世紀(jì)的數(shù)學(xué)家們研究哥德巴赫猜想所采用的主要方法,是篩法、圓法、密率法和三角和法等等高深的數(shù)學(xué)方法。解決這個(gè)猜想的思路,就像“縮小包圍圈”一樣,逐步逼近最后的結(jié)果?! ?920年,挪威數(shù)學(xué)家布朗證明了定理“9+9”,由此劃定了進(jìn)攻“哥德巴赫猜想”的“大包圍圈”。這個(gè)“9+9”是怎么回事呢?所謂“9+9”,翻譯成數(shù)學(xué)語(yǔ)言就是:“任何一個(gè)足夠大的偶數(shù),都可以表示成其它兩個(gè)數(shù)之和,而這兩個(gè)數(shù)中的每個(gè)數(shù),都是9個(gè)奇質(zhì)數(shù)之積?!?從這個(gè)“9+9”開(kāi)始,全世界的數(shù)學(xué)家集中力量“縮小包圍圈”,當(dāng)然最后的目標(biāo)就是“1+1”了?! ?924年,德國(guó)數(shù)學(xué)家雷德馬赫證明了定理“7+7”。很快,“6+6”、“5+5”、“4+4”和“3+3”逐一被攻陷。1957年,我國(guó)數(shù)學(xué)家王元證明了“2+3”。1962年,中國(guó)數(shù)學(xué)家潘承洞證明了“1+5”,同年又和王元合作證明了“1+4”。1965年,蘇聯(lián)數(shù)學(xué)家證明了“1+3”?! ?966年,我國(guó)著名數(shù)學(xué)家陳景潤(rùn)攻克了“1+2”,也就是:“任何一個(gè)足夠大的偶數(shù),都可以表示成兩個(gè)數(shù)之和,而這兩個(gè)數(shù)中的一個(gè)就是奇質(zhì)數(shù),另一個(gè)則是兩個(gè)奇質(zhì)數(shù)的積?!边@個(gè)定理被世界數(shù)學(xué)界稱(chēng)為“陳氏定理”?! ∮捎陉惥皾?rùn)的貢獻(xiàn),人類(lèi)距離哥德巴赫猜想的最后結(jié)果“1+1”僅有一步之遙了。但為了實(shí)現(xiàn)這最后的一步,也許還要?dú)v經(jīng)一個(gè)漫長(zhǎng)的探索過(guò)程。有許多數(shù)學(xué)家認(rèn)為,要想證明“1+1”,必須通過(guò)創(chuàng)造新的數(shù)學(xué)方法,以往的路很可能都是走不通的。2、四色問(wèn)題
3、哥德巴赫猜想
聯(lián)系客服