波曼的演算法

A. 堵丁柱的人物事跡

伯利克是個多霧的山城。早上，發動汽車前，要先擦去凝在風擋上的水珠。頭頂，總是陰沉沉的不見太陽。可是，駕車上山後，景觀卻大不一樣。籠罩著的伯利克和舊金山的雲霧已被踩到腳下。由陳省身創辦的數學所就坐落在加州大學伯利克校園背後的一座小山上。站著數學所的陽台上，你可以俯瞰整個伯利克城，遠眺舊金山的高檔大廈以及舉世聞名的金山大橋。
1985-1986年數學所以計算復雜性作為研究的主攻方向。這一年，有60多位實力雄厚的博士或即將獲得博士學位的研究生提出申請，最後只選了8名。堵丁柱在激烈的競爭中又一次獲勝，這成為聖巴巴拉數學系的一大新聞。系主任得到消息後馬上寫了一封賀信，每個教授見到他都表示了真誠的祝賀。
數學所在一座三層小樓里，樓內十分講究、舒適，充分體現了陳省身先生當初對設計者的要求：工作在這里，像置身於家中。每天下午3時，所里有一次點心和飲料供應，其目的是讓教授們有互相接觸的機會，堵丁柱和卡波、替米爾、銳本等著名教授就是在邊吃邊談中相識並加深友誼的，對年輕的博士後來說，這里稱得上是得天獨厚、令人神往的地方。
在伯克利數學所的工作經歷對一個數學家來說是重要的。這里節奏緊張，氣氛誘人。在一年的時間里，他大約寫了10篇論文。他與葛可一、龍格合作的關於單項函數和多項時間同構的重要工作就是在1985年9月在伯克利完成的。
單項函數在存在性是涉及密碼學的重大理論問題。當年的若干公共鑰匙密碼系統就是在假定這種函數的基礎上建立的。這樣，若單項函數不存在，這些系統也就不存在了。因此，對該問題的研究不僅具有理論意義，而且有經濟意義和軍事意義。多項式的時間同構問題是研究NP完全問題中產生的。NP完全問題是計算機科學中最重要的問題之一。1979年11月27日，《紐約時報》在報道哈契場演算法時誤認為NP完全問題已被解決，引起學術界大嘩。事實上，這一問題的答案不僅牽動著數學家和計算理論專家的心，而且牽動著許多經濟界和軍事界專家的心。
1975年波曼和哈特曼尼斯猜想，所有NP完全問題是多項式時間同構的。如果說該猜想被肯定，NP完全問題就可以解決。1982年，楊格和約瑟夫提出，這個猜測是否對，可能和單項函數的存在性有關。而堵丁柱等人的文章則第一次建立了兩者之間的關系，這就使得對多項式時間同構的研究進入了一個高潮。1986年，在伯克利舉辦的計算機復雜性年會，為這一方向舉辦專題討論會，會議的組織者，貝爾實驗室的馬哈尼博士在其後的論文中寫道：這兩篇論文的主要結果是這領域中的最重要先進成果，由兩文引入的技巧是有力的。