目前大家應(yīng)該是對(duì)諾貝爾數(shù)學(xué)獎(jiǎng)（2021年數(shù)學(xué)界）比較感興趣的，所以今天好房網(wǎng)小編CC就來(lái)為大家整理了一些關(guān)于諾貝爾數(shù)學(xué)獎(jiǎng)（2021年數(shù)學(xué)界）方面的相關(guān)知識(shí)來(lái)分享給大家，希望大家會(huì)喜歡哦。

諾貝爾數(shù)學(xué)獎(jiǎng)（2021年數(shù)學(xué)界）

作者 | 陳大鑫、維克多

編輯 | 青暮

3月17日晚，被譽(yù)為數(shù)學(xué)界“諾貝爾獎(jiǎng)”的阿貝爾獎(jiǎng)揭曉。

2021年挪威科學(xué)院決定將阿貝爾獎(jiǎng)授予來(lái)自匈牙利厄特沃什·羅蘭大學(xué)教授拉茲洛·洛瓦茲（László Lovász）和美國(guó)普林斯頓高等研究院教授艾維·維格森（Avi Wigderson）。

以表彰他們“對(duì)理論計(jì)算機(jī)科學(xué)和離散數(shù)學(xué)的基礎(chǔ)性貢獻(xiàn)，以及在將它們推動(dòng)至現(xiàn)代數(shù)學(xué)的中心領(lǐng)域方面的領(lǐng)導(dǎo)作用?！?/p>

阿貝爾獎(jiǎng)（Abel Prize）是挪威政府于 2001 年為紀(jì)念挪威著名數(shù)學(xué)家尼爾斯·亨利克·阿貝爾二百周年誕辰而設(shè)立的一項(xiàng)數(shù)學(xué)獎(jiǎng)，旨在表彰對(duì)數(shù)學(xué)領(lǐng)域擁有非凡深度和影響力的貢獻(xiàn)。2003 年6月3日，由挪威自然科學(xué)與文學(xué)院的五名數(shù)學(xué)家院士組成的委員會(huì)正式將該獎(jiǎng)項(xiàng)頒布給阿貝爾獎(jiǎng)第一位獲獎(jiǎng)?wù)?，此后每年頒布一次，750萬(wàn)挪威克朗（約合人民幣575萬(wàn)元）。

該獎(jiǎng)項(xiàng)與菲爾茲獎(jiǎng)、沃爾夫數(shù)學(xué)獎(jiǎng)并稱(chēng)國(guó)際數(shù)學(xué)界“三大獎(jiǎng)”。

迄今為止，阿貝爾獎(jiǎng)已擁有20多位獲獎(jiǎng)?wù)?，也成為了?guó)際所公認(rèn)的「數(shù)學(xué)界諾貝爾獎(jiǎng)」，也算是彌補(bǔ)諾貝爾科學(xué)獎(jiǎng)項(xiàng)中沒(méi)有數(shù)學(xué)獎(jiǎng)的遺憾——這也正是該獎(jiǎng)項(xiàng)設(shè)立的初衷之一。

1兩位理論計(jì)算機(jī)科學(xué)先驅(qū)

Lovász和Wigderson是理論計(jì)算機(jī)科學(xué)的先驅(qū)，其工作為從互聯(lián)網(wǎng)安全到網(wǎng)絡(luò)研究的應(yīng)用奠定了基礎(chǔ)。“他們都為理解計(jì)算中的隨機(jī)性和探索有效計(jì)算的邊界做出了根本性貢獻(xiàn)。”

Wigderson表示，該獎(jiǎng)項(xiàng)不僅驗(yàn)證了他自己工作的意義，而且還驗(yàn)證了計(jì)算理論的價(jià)值。他說(shuō)：“我認(rèn)為這對(duì)于該領(lǐng)域非常重要?！?/p>

2021年阿貝爾獎(jiǎng)獲得者Avi Wigderson（圖片來(lái)源：Dan Komoda /美國(guó)高等研究院，新澤西州普林斯頓）

Lovász說(shuō)：“如今，區(qū)分純數(shù)學(xué)和應(yīng)用數(shù)學(xué)越來(lái)越困難，而且我認(rèn)為這是一個(gè)很好的發(fā)展趨勢(shì)。”

2021年阿貝爾獎(jiǎng)獲得者László Lovász（來(lái)源：匈牙利科學(xué)院）

至少?gòu)墓畔ＥD時(shí)代開(kāi)始，算法就一直是數(shù)學(xué)的中心，哪怕是孩子在學(xué)校學(xué)習(xí)的簡(jiǎn)單程序（例如長(zhǎng)除法）。但是自從20世紀(jì)計(jì)算機(jī)問(wèn)世以來(lái)，研究的重點(diǎn)已經(jīng)從“一種算法可以解決這個(gè)問(wèn)題嗎？”變?yōu)椤耙环N算法，至少在原理上可以在真實(shí)的計(jì)算機(jī)上、合理的時(shí)間內(nèi)解決這個(gè)問(wèn)題”。

IAS的數(shù)學(xué)家Peter Sarnak表示，Lavaz和Wigderson在這個(gè)發(fā)展過(guò)程中發(fā)揮了核心作用。“算法復(fù)雜性理論和解決問(wèn)題速度的研究是在20世紀(jì)60年代和70年代發(fā)展起來(lái)的，他們被證明是該領(lǐng)域絕對(duì)的領(lǐng)導(dǎo)者?！?/p>

“在許多方面，他們的工作都是相輔相成的。Lovász是在數(shù)學(xué)方面，而Wigderson則是在計(jì)算機(jī)科學(xué)方面，但是他們研究的許多問(wèn)題都是相關(guān)的。”圣地亞哥大學(xué)加利福尼亞大學(xué)的計(jì)算機(jī)科學(xué)家Russell Impagliazzo說(shuō)，他與兩位研究人員都有過(guò)合作。

Lovász和Wigderson （Oslo 201 圖源Oberwolfach ）

2從數(shù)學(xué)到計(jì)算

Lovász于1948年出生在布達(dá)佩斯，在一個(gè)鼓勵(lì)有才華的孩子競(jìng)爭(zhēng)解決難題的環(huán)境中成長(zhǎng)。他從小就是數(shù)學(xué)明星，在十幾歲的時(shí)候，他就在國(guó)際數(shù)學(xué)奧林匹克競(jìng)賽上獲得了三枚金牌，并且在匈牙利的一場(chǎng)比賽表演中大獲全勝，這場(chǎng)比賽將數(shù)學(xué)神童放在玻璃隔離間中并挑戰(zhàn)他們自主解決難題的能力。

他的早期靈感大部分來(lái)自現(xiàn)代最多產(chǎn)的數(shù)學(xué)家Paul Erd?s。布達(dá)佩斯Alfréd Rényi數(shù)學(xué)研究所的數(shù)學(xué)家Péter Pál Pálfy說(shuō)，Erd?s的工作重點(diǎn)是離散對(duì)象（例如網(wǎng)絡(luò)中的節(jié)點(diǎn)）及其關(guān)系的數(shù)學(xué)，而不是幾何等領(lǐng)域中典型的連續(xù)變量。

Paul Erd?s將Lovász引入了圖論領(lǐng)域。當(dāng)時(shí)，圖論是數(shù)學(xué)上的死水領(lǐng)域，以提出諸如四色定理（現(xiàn)已被證明）之類(lèi)的有趣問(wèn)題而聞名，該定理是說(shuō)：任何一張地圖中最多僅用四種顏色就可以為國(guó)家/地區(qū)著色，而使得沒(méi)有兩個(gè)相鄰國(guó)家/地區(qū)使用相同的顏色。

“我不會(huì)說(shuō)它晦澀難懂，但是圖論最早肯定不是主流數(shù)學(xué)，因?yàn)樵S多問(wèn)題只是一些趣味性難題。”Lovász說(shuō)。但是，當(dāng)Lovász在1970年22歲時(shí)獲得博士學(xué)位時(shí)，情況已經(jīng)悄然發(fā)生了變化，一個(gè)主要原因是計(jì)算機(jī)科學(xué)的誕生和迅速發(fā)展。

計(jì)算機(jī)可以處理離散量（1和0的二進(jìn)制字符串），而組合學(xué)是離散對(duì)象的數(shù)學(xué)，它的主要子領(lǐng)域之一正是圖論，它研究連接頂點(diǎn)和邊構(gòu)成的網(wǎng)絡(luò)。因此，它為研究理論計(jì)算機(jī)科學(xué)中出現(xiàn)的很多問(wèn)題提供了一種強(qiáng)大的語(yǔ)言。

離散數(shù)學(xué)領(lǐng)域中的網(wǎng)絡(luò)理論曾經(jīng)被“純”數(shù)學(xué)家所鄙視，而如今它對(duì)其他數(shù)學(xué)領(lǐng)域和應(yīng)用（如大數(shù)據(jù)分析）都變得至關(guān)重要，Lovász的職業(yè)生涯就始于這個(gè)時(shí)期。他對(duì)基礎(chǔ)研究及其應(yīng)用頗感興趣，并且在微軟擔(dān)任全職研究人員長(zhǎng)達(dá)七年，擔(dān)任兩個(gè)學(xué)術(shù)職位。

Lovász將計(jì)算機(jī)和圖論的興起視為有利的歷史共識(shí)，可以與早于一個(gè)多世紀(jì)以前用于分析一個(gè)應(yīng)用物理問(wèn)題的方法（一種先進(jìn)的微積分形式）相提并論。Lovász說(shuō)：“我有時(shí)會(huì)類(lèi)比18和19世紀(jì)的分析和物理學(xué)，在這些領(lǐng)域中，它們是相互牽制的。而在圖論和計(jì)算機(jī)科學(xué)中也發(fā)生了類(lèi)似的事情?！?/p>

Lovász最著名的成果之一是他與兩位荷蘭數(shù)學(xué)理論家Arjen和Hendrik Lenstra一起設(shè)計(jì)的算法。這種被稱(chēng)為L(zhǎng)LL的算法將一個(gè)由整數(shù)組成的大向量分解為相同類(lèi)型的最短向量的總和。LLL算法適用于稱(chēng)為格的幾何對(duì)象，這些幾何對(duì)象是空間中的點(diǎn)集，其坐標(biāo)通常具有整數(shù)值。

LLL算法解決了有關(guān)其屬性的一個(gè)基本問(wèn)題：格中的哪個(gè)點(diǎn)最接近原點(diǎn)？這個(gè)簡(jiǎn)單的問(wèn)題通常很難解決，尤其是在涉及高維空間以及格中的點(diǎn)變形的情況下。LLL算法沒(méi)有完全解決問(wèn)題，而是找到了一個(gè)很好的近似解，確定了一個(gè)點(diǎn)并確保沒(méi)有其他點(diǎn)更接近原點(diǎn)。

由于此幾何模型的廣泛適用性，它在純數(shù)學(xué)的各個(gè)領(lǐng)域（比如分解多項(xiàng)式）都有應(yīng)用，并且對(duì)于數(shù)據(jù)加密的研究變得至關(guān)重要?；谡麛?shù)向量的密碼學(xué)密鑰被認(rèn)為對(duì)未來(lái)的互聯(lián)網(wǎng)安全性很重要，因?yàn)榕c當(dāng)今通信中通常使用的密鑰不同，人們認(rèn)為它們不會(huì)被未來(lái)的量子計(jì)算機(jī)所破解。

“這是基本算法之一。它在理論上很重要，并且有許多實(shí)際用途?！?IDC Herzliya和耶路撒冷希伯來(lái)大學(xué)的Gil Kalai說(shuō)，他曾是阿貝爾獎(jiǎng)委員會(huì)的成員。

Lovász最重要的另一個(gè)貢獻(xiàn)和概率有關(guān)。在1960年代，Paul Erd?s開(kāi)發(fā)了所謂的概率方法來(lái)回答有關(guān)圖的問(wèn)題。通常，數(shù)學(xué)家想知道是否存在具有某些屬性的圖?；卮疬@些問(wèn)題的一種方法是實(shí)際找到一個(gè)能滿(mǎn)足條件的圖形。但是Erd?s意識(shí)到另一種方法證明了隨機(jī)選擇的圖形將具有很高的概率具有此屬性。

不幸的是，Erd?s的概率方法僅在確定具有常見(jiàn)屬性的圖的存在方面效果最好。19世紀(jì)70年代，Lovász與Erd?s合作設(shè)計(jì)了一種補(bǔ)充技術(shù)，稱(chēng)為L(zhǎng)ovász局部引理，用于證明非常稀有的圖的存在。從那以后，它就成為了該領(lǐng)域的主要技術(shù)之一。

Lovász在其學(xué)術(shù)生涯中還解決了圖論中的許多其他難題，包括Kneser 猜想，即為某個(gè)圖著色所需的最小顏色數(shù)以及保證圖完美匹配和相關(guān)結(jié)構(gòu)的條件的問(wèn)題。他還自己提出了一些猜想，這些猜想如今仍在指導(dǎo)著圖論領(lǐng)域，其中包括兩個(gè)問(wèn)題，即KLS猜想和EFL猜想，它們?cè)谧罱鼛讉€(gè)月內(nèi)才取得了重大研究成果。

截至目前，Lovász已經(jīng)獲得了許多榮譽(yù)，包括1999年沃爾夫獎(jiǎng)、1999年克努斯獎(jiǎng)、2001年哥德?tīng)柂?jiǎng)和2010年京都獎(jiǎng)。

3從計(jì)算到數(shù)學(xué)

Wigderson于1956年出生于以色列海法。阿貝爾獎(jiǎng)的表彰認(rèn)可了他對(duì)計(jì)算機(jī)科學(xué)幾乎所有領(lǐng)域的貢獻(xiàn)，在其中他用可能找到的任何數(shù)學(xué)工具來(lái)解決任何問(wèn)題，即使對(duì)于看似遙遠(yuǎn)的研究領(lǐng)域也是如此。Sarnak說(shuō)，Wigderson對(duì)他的研究領(lǐng)域的熱情具有“傳染性”。

到他十幾歲的時(shí)候，計(jì)算機(jī)科學(xué)家才剛剛開(kāi)始草擬一個(gè)基本的理論框架，這個(gè)框架最終貫穿了他的大部分學(xué)術(shù)生涯。該框架稱(chēng)為復(fù)雜性理論，涉及基于算法難以解決的問(wèn)題對(duì)計(jì)算問(wèn)題進(jìn)行分類(lèi)。難度的主要衡量標(biāo)準(zhǔn)是計(jì)算步驟的數(shù)量，最基本的區(qū)別是“easy”與“hard”。

一個(gè)簡(jiǎn)單的計(jì)算問(wèn)題的示例是將兩個(gè)數(shù)字相乘。不管數(shù)量有多大，計(jì)算機(jī)都可以迅速找到乘積的。這個(gè)問(wèn)題屬于“ P”的復(fù)雜度類(lèi)中，它包含所有易于解決的計(jì)算問(wèn)題。

相比之下，找到一個(gè)數(shù)的質(zhì)因數(shù)是一個(gè)很難解決的計(jì)算問(wèn)題。沒(méi)有已知的算法可以快速分解所有數(shù)字。但是，如果告訴你一個(gè)數(shù)字的質(zhì)因數(shù)，就很容易驗(yàn)證它們是否正確。該問(wèn)題屬于“ NP”的復(fù)雜度類(lèi)，該類(lèi)包含可能難以解決但其答案易于驗(yàn)證的計(jì)算問(wèn)題。

1970年代初期，計(jì)算機(jī)科學(xué)家在計(jì)算復(fù)雜性領(lǐng)域制定了指導(dǎo)性猜想，詢(xún)問(wèn)P中的問(wèn)題列表是否恰好與NP中的問(wèn)題相對(duì)應(yīng)，即著名的”P(pán)/NP問(wèn)題“，這也是克雷數(shù)學(xué)研究所七個(gè)千禧年大獎(jiǎng)難題之一。

此問(wèn)題在1977年還很新穎，那時(shí)候Wigderson也進(jìn)入了以色列理工學(xué)院。隨后幾十年里，Wigderson對(duì)復(fù)雜性理論做出許多基礎(chǔ)性的貢獻(xiàn)，例如將一些復(fù)雜問(wèn)題進(jìn)行歸類(lèi)。

回顧過(guò)去，Wigderson說(shuō)：“當(dāng)我開(kāi)始讀研究生的時(shí)候，計(jì)算復(fù)雜性已經(jīng)慢慢開(kāi)始成熟了，在這期間，我自己對(duì)問(wèn)題的認(rèn)識(shí)也加深了”。

在20世紀(jì)80年代后期， Wigderson和Ran Raz合作嘗試解決計(jì)算機(jī)復(fù)雜性中的完美匹配問(wèn)題：假設(shè)有20臺(tái)機(jī)器，有20個(gè)任務(wù)待執(zhí)行，由于每臺(tái)機(jī)器只能完成這些任務(wù)的一部分，如何分配機(jī)器才能完成所有任務(wù)，且每臺(tái)機(jī)器只執(zhí)行一項(xiàng)任務(wù)。

Wigderson 和 Raz提出的解決思路是：加一些限制條件，假設(shè)工作在這個(gè)問(wèn)題上的計(jì)算機(jī)夠進(jìn)行大多數(shù)標(biāo)準(zhǔn)的計(jì)算運(yùn)算（如 "與"、 "或"），同時(shí)某些運(yùn)算是被禁止的，例如"非"。

當(dāng)然，計(jì)算機(jī)科學(xué)家最想證明的是，沒(méi)有條件約束下，一個(gè)計(jì)算問(wèn)題是hard。但到目前為止，他們還沒(méi)有做到這一點(diǎn)（否則我們就知道P是否等于NP）。因此相反，他們?cè)噲D證明，當(dāng)你限制計(jì)算資源和可用時(shí)間來(lái)解決匹配這樣的問(wèn)題時(shí)，不存在快速的算法。

Wigderson說(shuō)：“如果你想找到算法的局限性，當(dāng)在最一般的情況下無(wú)法做到時(shí)，就要加以限制，然后將一只胳膊綁在他們的背上?！?在1990年，他和Lovász證明，如果沒(méi)有數(shù)字電路中的邏輯“非”操作，則沒(méi)有很好的方法并行使用許多計(jì)算機(jī)來(lái)解決電路中的匹配問(wèn)題。

Wigderson自1999年以來(lái)一直在高等研究院進(jìn)行研究，他在復(fù)雜性理論方面取得了許多其他成果，其中包括一種稱(chēng)為之字形乘積的技術(shù)，該技術(shù)可以直接連接到純數(shù)學(xué)的多個(gè)領(lǐng)域，并提供了一種走迷宮策略，其中只需要跟蹤固定數(shù)量的交叉路口。Wigderson的工作廣度反映了自他加入以來(lái)，計(jì)算復(fù)雜性領(lǐng)域擴(kuò)展的方式。

Wigderson最著名的另一項(xiàng)成就是闡明了隨機(jī)性在計(jì)算中的作用。在許多情況下，例如尋找迷宮的出路，基于具有比喻性的硬幣翻轉(zhuǎn)現(xiàn)象使算法可以快速找到解決方案。Sarnak說(shuō)：“如果允許進(jìn)行隨機(jī)選擇，許多程序的運(yùn)行速度實(shí)際上會(huì)快得多。”

Wigderson及其合作者在1990年代發(fā)表的兩篇論文中證明，在某些假設(shè)下，始終可以將快速隨機(jī)算法轉(zhuǎn)換為快速確定性算法。這從理論上保證了隨機(jī)算法確實(shí)可以找到正確的解決方案。結(jié)果確定了被稱(chēng)為“ BPP”的復(fù)雜性類(lèi)與“ P”復(fù)雜性類(lèi)完全相同。它將數(shù)十年來(lái)對(duì)隨機(jī)算法的研究巧妙地結(jié)合到了復(fù)雜性理論的主體中，并改變了計(jì)算機(jī)科學(xué)家看待隨機(jī)算法的方式。

Wigderson的另一項(xiàng)主要工作在信息經(jīng)濟(jì)中變得越來(lái)越重要。它涉及“零知識(shí)證明（zero-knowledge proofs）”，這是一種允許某人在不透露任何有關(guān)文件內(nèi)容信息的情況下驗(yàn)證文件正確性的方法。

---

版權(quán)說(shuō)明：本文由用戶(hù)上傳，如有侵權(quán)請(qǐng)聯(lián)系刪除！

---

標(biāo)簽：