|
完全出人意料并与直觉相悖的是，这种验证所需扦验的数码个数可以达到很少的程度。这一理论是由苏丹、阿洛拉
、菲奇、戈德瓦泽、伦德、洛瓦兹、莫特瓦尼、萨弗拉和塞奇迪等人在一系列论文中发展起来的。由于此项研究，上述作者们共同荣获了2001年计算机协会的哥德尔奖。
苏丹还与其他研究者一起，对于理解某些问题解的不可逼近性作出了奠基性贡献。这项研究与理论计算机科学中一个著名的基本问题有关，这个基本问题是：p与np是否等同？粗略地讲，p是指所有用现有计算方法“容易”解决的问题。而np则包含了那些本质上更硬(更困难)的问题。术语“容易”在这里具有特定的技术涵义，涉及到解决问题的计算机算法的有效性。属于np的那些本质上困难的问题具有这样的特性：你可以容易地扦验已经提出的解答，但却找不到一个容易的算法从无到有地去算出一个解来。某些np硬问题是要寻找如下所述的组合问题的最优解：已给一个以有限集为元素的有限集合，求使其中任意两个集合都不相交的最大子集。苏丹和其他学者证明了：对于许多这样的问题来说，逼近最优解和寻找最优解是一样地困难。这一结果与概率可验证明的工作有密切联系。由于所涉及的问题大都与日常遇到的科学技术问题密切相关，这一结果在理论与实践两方面都具有重大意义。
苏丹有重要贡献的第三个领域是纠错码。这些码在保障各种各样的信息传输的安全和质量方面有重要作用----从cd音乐录制到互联网通讯到卫星传输。任何一种通信渠道都会夹有一定量的噪声，给需要传输的信息带来误差。冗余码被用来消除因噪声引起的误差，办法是将原来的信息改编成更大的信息。只要所编的信息在传输中误差不超过一定限度，接收者就能够复原原来的信息。冗余码会增加信息传输的费用，纠错码的科学与技巧正是要在冗余编码与经济效益之间寻找平衡。一类使用很广的码是里德-索罗门码（及其变种），发明于1960年代。40年来普遍认为这种码只能纠正数量有限的误差。通过创造一种新的译码算法，苏丹证明了里德-索罗门码能够纠正的误差比人们原先相象的要多得多。
迈杜·苏丹1969年9月12日生于印度马德拉斯（今切奈），1987年获新德里印度工学院计算机科学技术学士，1992年获伯克莱加州大学计算机科学博士学位。他曾在位于纽约约克城高地的托马斯--沃特森研究中心担任研究职务（1992—1997），目前是麻省理工学院电子工程与计算机科学系副教授。 |
