計算複雜性的理論和套用

《計算複雜性的理論和套用》是依託中國科學院數學與系統科學研究院，由堵丁柱擔任項目負責人的重點項目。

基本介紹

• 中文名：計算複雜性的理論和套用
• 項目類別：重點項目
• 項目負責人：堵丁柱
• 依託單位：中國科學院數學與系統科學研究院
• 批准號：19331050
• 申請代碼：A0410
• 負責人職稱：研究員
• 研究期限：1994-01-01 至 1998-12-31
• 支持經費：16（萬元）

項目摘要

本項目關於計算複雜性的研究主要分為理論和套用兩個方面。在理論部分，主要考慮基於制定時模型的計算複雜的問題。特別是驗證了甲約斯特和維拉明猜想的正確性（n=6,10）。在套用部分，主要考慮的是最小斯坦納樹和，網路及其相關的網路最佳化設計問題，另外也探討了克勞斯網路在多頻率環境下的多種非阻塞性。主要結果分為網路的結構性分析和近似算法的設計。特別是分別證明了塞斯利克和格塞厄姆關於斯坦納比的兩個重要猜想。此外，分別堆翻了有關與斯密斯關於生成斯坦納樹的貪婪算法的猜想，同時推翻了厄爾伯特與鮑拉克斯坦納比可以在正規單純的上述到的猜想.