百科详情

　　堵丁柱教授，11949年出生在齐齐哈尔市，978年在东北重型机械学院（今燕山大学）计算机系学习，1982年获中国科学院硕士学位，1985年获美国加里弗尼亚大学圣巴巴拉分校博士学位。1985年～1986年在美国加州伯克利数学科学研究院作博士后，1986～1987年在美国麻省理工大学数学系作访问学者，1987年任中国科学院应用数学所教授。他先后在美国伯克利大学（Berkeley）， 麻省理工大学, 普林斯顿大学数学研究所工作。1991年和1995年成为 Minnesota大学计算机系的副教授和教授。 并于1998到1999年之间任职香港城市大学计算机科学系访问教授。 1987-2002年为中国科学院应用数学所研究员。

　　堵丁柱教授现任Texas 大学计算机系教授，美国自然科学基金委计算机理论的项目主管，也是西安交通大学教授。 他的研究方向包括组合优化，计算机网络和计算理论。

　　堵丁柱教授已经发表论文60多篇， 出版了20本书。 他是组合优化杂志和系列书籍《网络理论和应用》的主编， 是超过15个杂志的编委。 1998年获得美国INFORMS的CSTS奖，1993年获得中国自然科学二等奖， 1992年获得中国科学院自然科学一等奖。

　　为了汲取西方新的知识，堵丁柱研究员1990年2月再次出国，在美国普林斯顿大学作访问学者。才一个多月，即4月10日，他就和美国贝尔实验室黄光明研究员合作攻克了吉尔伯特——波雷克猜想，即斯坦纳比难题。所以堵丁柱研究员说，这个结果是在国外做完的，但是大量研究工作实际是在国内做的。1990年10月正式公布以后，没想到会引起国际数学界那样广泛注意和强烈反响，被列为1989年-1990年度美国离散数学界和理论计算机科学界重大成果。英国大百科全书在收录这一成果时也评价说：“在过去的一年里，数学上最显著的进展包括长期、著名的猜想——一个最短网络的猜想……这个猜想就是斯坦纳比问题。”

　　什么是斯坦纳比问题呢？假设我们在北京、上海、西安三城市之间架设电话线，一种办法是分别联通北京——上海和北京——西安。另一种办法是选第四个点，假设郑州。由此分别向三城市架线，可能你不会想到第二种办法所用的电话线只是第一种办法的86.6%，即可取得比第一种办法节约13%的显著经济效益。这就是离散数学界30年代提出的著名的斯坦纳比问题，但一直未能得到证明。直到1967年大名鼎鼎的贝尔电话公司，遇上了一家精明的用户航空公司，竟被戳了一个大窟窿。这家用户要求在第四个点的位置上架上电话线。这样使得电话公司不仅要拉新线，增加服务网点，而且要减少收费。这件事的连锁反应迫使电话公司改变了坚持长达10年按照最少发生树长度收费的原则，并且不得不对最短网络问题进行研究。于是，贝尔实验室数学中心主任波雷克和研究员吉尔伯特对斯坦纳比问题作了许多研究，根据自己多年研究所得提出如下猜想：对欧氏平面上的任何有限点集，其最小的Steiner树同最小发生树的长度之比（称为Steiner比，即斯坦纳比）不小于√3/2.换言之，正三角形加点可以节省最多。但他们自己并没有能证明它。

　　由于其在运输、通信和计算机等现代经济与科技中的重要作用，近几十年来它的研究进展越来越快。1985年，格拉姆和金芳容借助于计算机进行了大量运算，证明了斯坦纳比大于0.824，虽距0.866不遥远，却始终未能达到最终目标。美国数学会主席曾感叹道：“这问题已经公开了22年，这件事总令你不安，你不能证明这样初级的东西。”也许源于猜想提出的戏剧性背景，也许源于理论意义以及贝尔实验室的学术权威，也许源于数学家对形成初等而又难解问题的爱好，人们对这个问题的研究历久不衰。

　　1990年，41岁的堵丁柱因为攻克这一问题而成为世界数学界冒出的奇葩。他与贝尔实验室黄光明研究员合作，找到了一个全新途径，给出了吉尔伯特-波雷克猜想完整的证明。证明的核心是关于鞍点的一个定理。其主要思想是，首先在欧氏平面含n点的集合与2n-3维空间的点之间建立一一对应的关系，使得猜想可以化为2n-3维空间上函数的极值问题。然后利用鞍点定理找出可以达到极值的临界点应满足的必要条件。之后，再将此条件转换为临界点对应的点集上的几何性质。最后，利用这几何性质确定几何结构，验证该猜想。一个重要的注释是，为获得较易验证的几何结构，他们将猜想先转换为一个较强的形式，然后再如上法炮制。

　　证明于1990年10月在会议上正式公开，《纽约时报》立刻做了报道。接着《科学》杂志、《科学新闻》《新科学论》《SLAM新闻》等报刊上出现了许多报道。值得提及的《SLAM新闻》在头版上用了个有趣的“在计算机时代欧氏几何的欧氏平面上n点的集合←→2n-3维空间的点力与运气”。在《不列颠百科全书1992年鉴》中，该证明进一步被列为入选的6项数学成果的第一项。因此，堵丁柱也荣获了中国科学院自然科学一等奖、国家科技进步二等奖和中国青年科学家奖等殊荣。

　　Stewart教授对证明的意义作了阐述。12年前曾当过堵丁柱的老师，12年后又配合堵丁柱攻克斯坦纳比难题的贝尔实验室研究员黄光明在兴奋之余撰文记述了研究过程。他幽默地写道：“如果要等我证出0.866的猜想才退休，那我可能要在贝尔实验室过百岁生日了。解决这一问题的关键也许不在时间而在人，我能做的贡献是找到一个比我强的人来作此问题。我找到了堵丁柱，而堵丁柱今年四月找到了答案。”

　　每个成功者的背后，都会留下奋斗的足迹。探索一下堵丁柱的成才之路，或许对今天的青年朋友有所启迪。

　　1996年堵的老师越民义在《运筹学杂志》发表文章，否定了堵的工作。

　　伯利克是个多雾的山城。早上，发动汽车前，要先擦去凝在风挡上的水珠。头顶，总是阴沉沉的不见太阳。可是，驾车上山后，景观却大不一样。笼罩着的伯利克和旧金山的云雾已被踩到脚下。由陈省身创办的数学所就坐落在加州大学伯利克校园背后的一座小山上。站着数学所的阳台上，你可以俯瞰整个伯利克城，远眺旧金山的高档大厦以及举世闻名的金山大桥。

　　1985-1986年数学所以计算复杂性作为研究的主攻方向。这一年，有60多位实力雄厚的博士或即将获得博士学位的研究生提出申请，最后只选了8名。堵丁柱在激烈的竞争中又一次获胜，这成为圣巴巴拉数学系的一大新闻。系主任得到消息后马上写了一封贺信，每个教授见到他都表示了真诚的祝贺。

　　数学所在一座三层小楼里，楼内十分讲究、舒适，充分体现了陈省身先生当初对设计者的要求：工作在这里，像置身于家中。每天下午3时，所里有一次点心和饮料供应，其目的是让教授们有互相接触的机会，堵丁柱和卡波、替米尔、锐本等著名教授就是在边吃边谈中相识并加深友谊的，对年轻的博士后来说，这里称得上是得天独厚、令人神往的地方。

　　在伯克利数学所的工作经历对一个数学家来说是重要的。这里节奏紧张，气氛诱人。在一年的时间里，他大约写了10篇论文。他与葛可一、龙格合作的关于单项函数和多项时间同构的重要工作就是在1985年9月在伯克利完成的。

　　单项函数在存在性是涉及密码学的重大理论问题。当年的若干公共钥匙密码系统就是在假定这种函数的基础上建立的。这样，若单项函数不存在，这些系统也就不存在了。因此，对该问题的研究不仅具有理论意义，而且有经济意义和军事意义。多项式的时间同构问题是研究NP完全问题中产生的。NP完全问题是计算机科学中最重要的问题之一。1979年11月27日，《纽约时报》在报道哈契场算法时误认为NP完全问题已被解决，引起学术界大哗。事实上，这一问题的答案不仅牵动着数学家和计算理论专家的心，而且牵动着许多经济界和军事界专家的心。

　　1975年波曼和哈特曼尼斯猜想，所有NP完全问题是多项式时间同构的。如果说该猜想被肯定，NP完全问题就可以解决。1982年，杨格和约瑟夫提出，这个猜测是否对，可能和单项函数的存在性有关。而堵丁柱等人的文章则第一次建立了两者之间的关系，这就使得对多项式时间同构的研究进入了一个高潮。1986年，在伯克利举办的计算机复杂性年会，为这一方向举办专题讨论会，会议的组织者，贝尔实验室的马哈尼博士在其后的论文中写道：这两篇论文的主要结果是这领域中的最重要先进成果，由两文引入的技巧是有力的。

　　1986-1987年是伯利克数学所的代数数论年，搞计算复杂性的学者们便各奔东西了。堵丁柱接受麻省理学的聘请，以访问助理教授的身份开始了与克拉依曼教授的合作。事隔4年从不能接收作正式研究生到可以作助理教授，变化之大，令人感慨万端。

　　麻省理工学院是一所举世闻名的大学，它座落在查理士河畔，与波士顿的高大建筑群隔河相望。楼内走廊的墙上，挂满了为科学技术作出重大贡献的教授们的历史图片，这使人一进其中，就体验到它的历史悠久和硕果累累。在应用数学方面享有很高声望的林加翘教授就在这里工作。幸运的是，堵丁柱的办公室被安排在林教授的斜对面，使他有机会经常当面聆听先生的教诲。在教书之余，堵丁柱充分利用业余时间，同这里的教授和访问学者们探讨问题。在此期间，他完成了9篇论文，并在另外的项目上也取得了有意义的进展。

　　在麻省理工学院期间，堵丁柱和章祥荪合作的罗素梯度投影收敛的论文刊印出来了。

　　罗素梯度投影方法是解决带约束非线性规划问题的基本方法。自1960年罗素提出这个方法以来，收敛问题一直没有解决。此后，几乎每个讨论该方法的教科书都要提及这个问题，使这个问题成为非线性规划领域中较有名的长期未解决的问题之一。早在1980年，在越民义教授和韩继业教授的指导下，堵丁柱对罗素投影法曾作过较系统的学习和研究，在硕士毕业论文中，又解决了梯度投影的退化处理问题。在此后的工作中，他又简化了由泡拉克提出、章祥荪教授改进的一种罗素梯度投影法的变形，并且以反例证实了在某种特殊情况下，原算法是可以不收敛的。1986年刊出的与章祥荪教授合作的论文是在1984年完成的，这篇论文的主要结论是，一般说来，罗素算法提供的技巧是可以使算法收敛的。因此，基本解决了这个问题。罗素本人在后来的一封信中肯定了他们的工作。他写道，我想祝贺你们，你们最近的工作，最终解决了和我的原始论文相关联的收敛性问题。

　　在堵丁柱的论文目录分类中有可靠性理论题目。他对这方面的研究是从证明德曼·勒伯曼和罗斯猜测开始的。他们的猜测是关一种概率模型中几个性质相同但工作概率不同的部件的最优分配。堵丁柱与黄光明合作，在1982年年初得出完全的证明，并且建立了一些较一般的定理用于解决最优分配的问题。在纽约期弟文斯工学院举办的可靠性会议上，他被邀请报告了该问题及有关成果。

　　在麻省理学院的研究工作中，堵丁柱给克拉依曼教授印象最深的是关于他本人的一个猜测的证明。这个猜测是关于曼哈顿格中具有给定直径最大的集约性质。教授万没有想到，这位中国学者在证明中使用了与他提出猜测论文中相同的技巧，在不长的时间里却获得了出人意外的成功。