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