《NP最優問題的機率近似算法設計和平均複雜性設計》是依託復旦大學，由朱洪擔任項目負責人的面上項目。
基本介紹
- 中文名：NP最優問題的機率近似算法設計和平均複雜性設計
- 依託單位：復旦大學
- 項目類別：面上項目
- 項目負責人：朱洪
- 批准號：69673038
- 申請代碼：F0201
- 負責人職稱：教授
- 研究期限：1997-01-01 至 1999-12-31
- 支持經費：9（萬元）
項目摘要
本項目主要對於NP最優問題的隨機算法，近似算法及平均複雜性和用於計算機安全領域的數論算法的隨機性分析和平均複雜性進行研究。對於NP最佳化問題給出了一種新的歸約和邏輯定義，使得對數近似度的NP最佳化總是從常數近似度及多項式近似度的NP最佳化問題中分離出來。對集合論和圖論中的某些經典問題給出了新的隨機和褪隨機算法。從計算複雜性的角度對零知識證明進行了較為深入的研究並給出了一個隨機自歸約的四步零知識證明協定並給出了新的可靠性定義。此外，對計算複雜性尤其平均複雜性在構造安全的系統的套用給予了探討，並基於此給出了幾種安全的系統構造方案。
