波曼的算法

A. 堵丁柱的人物事迹

伯利克是个多雾的山城。早上，发动汽车前，要先擦去凝在风挡上的水珠。头顶，总是阴沉沉的不见太阳。可是，驾车上山后，景观却大不一样。笼罩着的伯利克和旧金山的云雾已被踩到脚下。由陈省身创办的数学所就坐落在加州大学伯利克校园背后的一座小山上。站着数学所的阳台上，你可以俯瞰整个伯利克城，远眺旧金山的高档大厦以及举世闻名的金山大桥。
1985-1986年数学所以计算复杂性作为研究的主攻方向。这一年，有60多位实力雄厚的博士或即将获得博士学位的研究生提出申请，最后只选了8名。堵丁柱在激烈的竞争中又一次获胜，这成为圣巴巴拉数学系的一大新闻。系主任得到消息后马上写了一封贺信，每个教授见到他都表示了真诚的祝贺。
数学所在一座三层小楼里，楼内十分讲究、舒适，充分体现了陈省身先生当初对设计者的要求：工作在这里，像置身于家中。每天下午3时，所里有一次点心和饮料供应，其目的是让教授们有互相接触的机会，堵丁柱和卡波、替米尔、锐本等着名教授就是在边吃边谈中相识并加深友谊的，对年轻的博士后来说，这里称得上是得天独厚、令人神往的地方。
在伯克利数学所的工作经历对一个数学家来说是重要的。这里节奏紧张，气氛诱人。在一年的时间里，他大约写了10篇论文。他与葛可一、龙格合作的关于单项函数和多项时间同构的重要工作就是在1985年9月在伯克利完成的。
单项函数在存在性是涉及密码学的重大理论问题。当年的若干公共钥匙密码系统就是在假定这种函数的基础上建立的。这样，若单项函数不存在，这些系统也就不存在了。因此，对该问题的研究不仅具有理论意义，而且有经济意义和军事意义。多项式的时间同构问题是研究NP完全问题中产生的。NP完全问题是计算机科学中最重要的问题之一。1979年11月27日，《纽约时报》在报道哈契场算法时误认为NP完全问题已被解决，引起学术界大哗。事实上，这一问题的答案不仅牵动着数学家和计算理论专家的心，而且牵动着许多经济界和军事界专家的心。
1975年波曼和哈特曼尼斯猜想，所有NP完全问题是多项式时间同构的。如果说该猜想被肯定，NP完全问题就可以解决。1982年，杨格和约瑟夫提出，这个猜测是否对，可能和单项函数的存在性有关。而堵丁柱等人的文章则第一次建立了两者之间的关系，这就使得对多项式时间同构的研究进入了一个高潮。1986年，在伯克利举办的计算机复杂性年会，为这一方向举办专题讨论会，会议的组织者，贝尔实验室的马哈尼博士在其后的论文中写道：这两篇论文的主要结果是这领域中的最重要先进成果，由两文引入的技巧是有力的。