1.P（多項(xiàng)式算法）問(wèn)題對(duì)NP（非多項(xiàng)式算法）問(wèn)題
在一個(gè)周六的晚上,你參加了一個(gè)盛大的晚會(huì).由于感到局促不安,你想知道這一大廳中是否有你已經(jīng)認(rèn)識(shí)的人.你的主人向你提議說(shuō),你一定認(rèn)識(shí)那位正在甜點(diǎ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è)例子.與此類似的是,如果某人告訴你,數(shù)13,717,421可以寫成兩個(gè)較小的數(shù)的乘積,你可能不知道是否應(yīng)該相信他,但是如果他告訴你它可以因子分解為3607乘上3803,那么你就可以用一個(gè)袖珍計(jì)算器容易驗(yàn)證這是對(duì)的.不管我們編寫程序是否靈巧,判定一個(gè)答案是可以很快利用內(nèi)部知識(shí)來(lái)驗(yàn)證,還是沒(méi)有這樣的提示而需要花費(fèi)大量時(shí)間來(lái)求解,被看作邏輯和計(jì)算機(jī)科學(xué)中最突出的問(wèn)題之一.它是斯蒂文·考克（StephenCook）于1971年陳述的.
2.霍奇(Hodge)猜想
二十世紀(jì)的數(shù)學(xué)家們發(fā)現(xiàn)了研究復(fù)雜對(duì)象的形狀的強(qiáng)有力的辦法.基本想法是問(wèn)在怎樣的程度上,我們可以把給定對(duì)象的形狀通過(guò)把維數(shù)不斷增加的簡(jiǎn)單幾何營(yíng)造塊粘合在一起來(lái)形成.這種技巧是變得如此有用,使得它可以用許多不同的方式來(lái)推廣；最終導(dǎo)至一些強(qiáng)有力的工具,使數(shù)學(xué)家在對(duì)他們研究中所遇到的形形色色的對(duì)象進(jìn)行分類時(shí)取得巨大的進(jìn)展.不幸的是,在這一推廣中,程序的幾何出發(fā)點(diǎn)變得模糊起來(lái).在某種意義下,必須加上某些沒(méi)有任何幾何解釋的部件.霍奇猜想斷言,對(duì)于所謂射影代數(shù)簇這種特別完美的空間類型來(lái)說(shuō),稱作霍奇閉鏈的部件實(shí)際上是稱作代數(shù)閉鏈的幾何部件的(有理線性)組合.
3.龐加萊(Poincare)猜想
如果我們伸縮圍繞一個(gè)蘋果表面的橡皮帶,那么我們可以既不扯斷它,也不讓它離開(kāi)表面,使它慢慢移動(dòng)收縮為一個(gè)點(diǎn).另一方面,如果我們想象同樣的橡皮帶以適當(dāng)?shù)姆较虮簧炜s在一個(gè)輪胎面上,那么不扯斷橡皮帶或者輪胎面,是沒(méi)有辦法把它收縮到一點(diǎn)的.我們說(shuō),蘋果表面是“單連通的”,而輪胎面不是.大約在一百年以前,龐加萊已經(jīng)知道,二維球面本質(zhì)上可由單連通性來(lái)刻畫,他提出三維球面(四維空間中與原點(diǎn)有單位距離的點(diǎn)的全體)的對(duì)應(yīng)問(wèn)題.這個(gè)問(wèn)題立即黎曼(Riemann)假設(shè) 有些數(shù)具有不能表示為兩個(gè)更小的數(shù)的乘積的特殊性質(zhì),例如,2,3,5,7,等等.這樣的數(shù)稱為素?cái)?shù)；它們?cè)诩償?shù)學(xué)及其應(yīng)用中都起著重要作用.在所有自然數(shù)中,這種素?cái)?shù)的分布并不遵循任何有規(guī)則的模式；然而,德國(guó)數(shù)學(xué)家黎曼(1826~1866)觀察到,素?cái)?shù)的頻率緊密相關(guān)于一個(gè)精心構(gòu)造的所謂黎曼蔡塔函數(shù)z(s$的性態(tài).著名的黎曼假設(shè)斷言,方程z(s)=0的所有有意義的解都在一條直線上.這點(diǎn)已經(jīng)對(duì)于開(kāi)始的1,500,000,000個(gè)解驗(yàn)證過(guò).證明它對(duì)于每一個(gè)有意義的解都成立將為圍繞素?cái)?shù)分布的許多奧秘帶來(lái)光明.變得無(wú)比困難,從那時(shí)起,數(shù)學(xué)家們就在為此奮斗.
4.黎曼(Riemann)假設(shè)
有些數(shù)具有不能表示為兩個(gè)更小的數(shù)的乘積的特殊性質(zhì),例如,2,3,5,7,等等.這樣的數(shù)稱為素?cái)?shù)；它們?cè)诩償?shù)學(xué)及其應(yīng)用中都起著重要作用.在所有自然數(shù)中,這種素?cái)?shù)的分布并不遵循任何有規(guī)則的模式；然而,德國(guó)數(shù)學(xué)家黎曼(1826~1866)觀察到,素?cái)?shù)的頻率緊密相關(guān)于一個(gè)精心構(gòu)造的所謂黎曼蔡塔函數(shù)z(s$的性態(tài).著名的黎曼假設(shè)斷言,方程z(s)=0的所有有意義的解都在一條直線上.這點(diǎn)已經(jīng)對(duì)于開(kāi)始的1,500,000,000個(gè)解驗(yàn)證過(guò).證明它對(duì)于每一個(gè)有意義的解都成立將為圍繞素?cái)?shù)分布的許多奧秘帶來(lái)光明.
5.楊－米爾斯(Yang-Mills)存在性和質(zhì)量缺口
量子物理的定律是以經(jīng)典力學(xué)的牛頓定律對(duì)宏觀世界的方式對(duì)基本粒子世界成立的.大約半個(gè)世紀(jì)以前,楊振寧和米爾斯發(fā)現(xiàn),量子物理揭示了在基本粒子物理與幾何對(duì)象的數(shù)學(xué)之間的令人注目的關(guān)系.基于楊－米爾斯方程的預(yù)言已經(jīng)在如下的全世界范圍內(nèi)的實(shí)驗(yàn)室中所履行的高能實(shí)驗(yàn)中得到證實(shí)：布羅克哈文、斯坦福、歐洲粒子物理研究所和筑波.盡管如此,他們的既描述重粒子、又在數(shù)學(xué)上嚴(yán)格的方程沒(méi)有已知的解.特別是,被大多數(shù)物理學(xué)家所確認(rèn)、并且在他們的對(duì)于 “夸克”的不可見(jiàn)性的解釋中應(yīng)用的“質(zhì)量缺口”假設(shè),從來(lái)沒(méi)有得到一個(gè)數(shù)學(xué)上令人滿意的證實(shí).在這一問(wèn)題上的進(jìn)展需要在物理上和數(shù)學(xué)上兩方面引進(jìn)根本上的新觀念.
6.納維葉－斯托克斯(Navier-Stokes)方程的存在性與光滑性
起伏的波浪跟隨著我們的正在湖中蜿蜒穿梭的小船,湍急的氣流跟隨著我們的現(xiàn)代噴氣式飛機(jī)的飛行.數(shù)學(xué)家和物理學(xué)家深信,無(wú)論是微風(fēng)還是湍流,都可以通過(guò)理解納維葉－斯托克斯方程的解,來(lái)對(duì)它們進(jìn)行解釋和預(yù)言.雖然這些方程是19世紀(jì)寫下的,我們對(duì)它們的理解仍然極少.挑戰(zhàn)在于對(duì)數(shù)學(xué)理論作出實(shí)質(zhì)性的進(jìn)展,使我們能解開(kāi)隱藏在納維葉－斯托克斯方程中的奧秘.
7.貝赫(Birch)和斯維訥通－戴爾(Swinnerton-Dyer)猜想
數(shù)學(xué)家總是被諸如x^2+y^2=z^2那樣的代數(shù)方程的所有整數(shù)解的刻畫問(wèn)題著迷.歐幾里德曾經(jīng)對(duì)這一方程給出完全的解答,但是對(duì)于更為復(fù)雜的方程,這就變得極為困難.事實(shí)上,正如馬蒂雅謝維奇(Yu.V.Matiyasevich)指出,希爾伯特第十問(wèn)題是不可解的,即,不存在一般的方法來(lái)確定這樣的方法是否有一個(gè)整數(shù)解.當(dāng)解是一個(gè)阿貝爾簇的點(diǎn)時(shí),貝赫和斯維訥通－戴爾猜想認(rèn)為,有理點(diǎn)的群的大小與一個(gè)有關(guān)的蔡塔函數(shù)z(s)在點(diǎn)s=1附近的性態(tài).特別是,這個(gè)有趣的猜想認(rèn)為,如果z(1)等于0,那么存在無(wú)限多個(gè)有理點(diǎn)(解),相反,如果z(1)不等于0,那么只存在有限多個(gè)這樣的點(diǎn).
8.幾何尺規(guī)作圖問(wèn)題
這里所說(shuō)的“幾何尺規(guī)作圖問(wèn)題”是指做圖限制只能用直尺、圓規(guī),而這里的直尺是指沒(méi)有刻度只能畫直線的尺.“幾何尺規(guī)作圖問(wèn)題”包括以下四個(gè)問(wèn)題 1.化圓為方－求作一正方形使其面積等於一已知圓； 2.三等分任意角； 3.倍立方－求作一立方體使其體積是一已知立方體的二倍. 4.做正十七邊形. 以上四個(gè)問(wèn)題一直困擾數(shù)學(xué)家二千多年都不得其解,而實(shí)際上這前三大問(wèn)題都已證明不可能用直尺圓規(guī)經(jīng)有限步驟可解決的.第四個(gè)問(wèn)題是高斯用代數(shù)的方法解決的,他也視此為生平得意之作,還交待要把正十七邊形刻在他的墓碑上,但后來(lái)他的墓碑上并沒(méi)有刻上十七邊形,而是十七角星,因?yàn)樨?fù)責(zé)刻碑的雕刻家認(rèn)為,正十七邊形和圓太像了,大家一定分辨不出來(lái).
9.哥德巴赫猜想
公元1742年6月7日哥德巴赫(Goldbach)寫信給當(dāng)時(shí)的大數(shù)學(xué)家歐拉(Euler),提出了以下的猜想: (a) 任何一個(gè)>=6之偶數(shù),都可以表示成兩個(gè)奇質(zhì)數(shù)之和. (b) 任何一個(gè)>=9之奇數(shù),都可以表示成三個(gè)奇質(zhì)數(shù)之和. 從此,這道著名的數(shù)學(xué)難題引起了世界上成千上萬(wàn)數(shù)學(xué)家的注意.200年過(guò)去了,沒(méi)有人證明它.哥德巴赫猜想由此成為數(shù)學(xué)皇冠上一顆可望不可及的“明珠”.
10.四色猜想
1852年,畢業(yè)于倫敦大學(xué)的弗南西斯.格思里來(lái)到一家科研單位搞地圖著色工作時(shí),發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái),每幅地圖都可以用四種顏色著色,使得有共同邊界的國(guó)家著上不同的顏色.” 1872年,英國(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). 1976年,美國(guó)數(shù)學(xué)家阿佩爾與哈肯在美國(guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上,用了1200個(gè)小時(shí),作了100億判斷,終于完成了四色定理的證明.四色猜想的計(jì)算機(jī)證明,轟動(dòng)了世界.