完全出人意料并與直覺相悖的是，這種驗(yàn)證所需扦驗(yàn)的數(shù)碼個(gè)數(shù)可以達(dá)到很少的程度。這一理論是由蘇丹、阿洛拉
、菲奇、戈德瓦澤、倫德、洛瓦茲、莫特瓦尼、薩弗拉和塞奇迪等人在一系列論文中發(fā)展起來的。由于此項(xiàng)研究，上述作者們共同榮獲了2001年計(jì)算機(jī)協(xié)會(huì)的哥德爾獎(jiǎng)。
蘇丹還與其他研究者一起，對(duì)于理解某些問題解的不可逼近性作出了奠基性貢獻(xiàn)。這項(xiàng)研究與理論計(jì)算機(jī)科學(xué)中一個(gè)著名的基本問題有關(guān)，這個(gè)基本問題是：p與np是否等同？粗略地講，p是指所有用現(xiàn)有計(jì)算方法“容易”解決的問題。而np則包含了那些本質(zhì)上更硬(更困難)的問題。術(shù)語(yǔ)“容易”在這里具有特定的技術(shù)涵義，涉及到解決問題的計(jì)算機(jī)算法的有效性。屬于np的那些本質(zhì)上困難的問題具有這樣的特性：你可以容易地扦驗(yàn)已經(jīng)提出的解答，但卻找不到一個(gè)容易的算法從無到有地去算出一個(gè)解來。某些np硬問題是要尋找如下所述的組合問題的最優(yōu)解：已給一個(gè)以有限集為元素的有限集合，求使其中任意兩個(gè)集合都不相交的最大子集。蘇丹和其他學(xué)者證明了：對(duì)于許多這樣的問題來說，逼近最優(yōu)解和尋找最優(yōu)解是一樣地困難。這一結(jié)果與概率可驗(yàn)證明的工作有密切聯(lián)系。由于所涉及的問題大都與日常遇到的科學(xué)技術(shù)問題密切相關(guān)，這一結(jié)果在理論與實(shí)踐兩方面都具有重大意義。
蘇丹有重要貢獻(xiàn)的第三個(gè)領(lǐng)域是糾錯(cuò)碼。這些碼在保障各種各樣的信息傳輸?shù)陌踩唾|(zhì)量方面有重要作用----從cd音樂錄制到互聯(lián)網(wǎng)通訊到衛(wèi)星傳輸。任何一種通信渠道都會(huì)夾有一定量的噪聲，給需要傳輸?shù)男畔碚`差。冗余碼被用來消除因噪聲引起的誤差，辦法是將原來的信息改編成更大的信息。只要所編的信息在傳輸中誤差不超過一定限度，接收者就能夠復(fù)原原來的信息。冗余碼會(huì)增加信息傳輸?shù)馁M(fèi)用，糾錯(cuò)碼的科學(xué)與技巧正是要在冗余編碼與經(jīng)濟(jì)效益之間尋找平衡。一類使用很廣的碼是里德-索羅門碼（及其變種），發(fā)明于1960年代。40年來普遍認(rèn)為這種碼只能糾正數(shù)量有限的誤差。通過創(chuàng)造一種新的譯碼算法，蘇丹證明了里德-索羅門碼能夠糾正的誤差比人們?cè)认嘞蟮囊嗟枚唷?/p>
邁杜·蘇丹1969年9月12日生于印度馬德拉斯（今切奈），1987年獲新德里印度工學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)士，1992年獲伯克萊加州大學(xué)計(jì)算機(jī)科學(xué)博士學(xué)位。他曾在位于紐約約克城高地的托馬斯--沃特森研究中心擔(dān)任研究職務(wù)（1992—1997），目前是麻省理工學(xué)院電子工程與計(jì)算機(jī)科學(xué)系副教授。 |
