《參數複雜性理論的研究》是依託上海交通大學，由陳翌佳擔任項目負責人的面上項目。
基本介紹
- 中文名：參數複雜性理論的研究
- 項目類別：面上項目
- 項目負責人：陳翌佳
- 依託單位：上海交通大學
- 批准號：60673049
- 申請代碼：F0201
- 負責人職稱：教授
- 研究期限：2007-01-01 至 2009-12-31
- 支持經費：24（萬元）
項目摘要
參數複雜性是一種較為新穎的複雜性理論框架。它基於以下的考察：很多實際問題的輸入蘊含豐富的結構信息，例如對於資料庫查詢問題，它的輸入包含兩個部分：一個資料庫和一個查詢。而我們知道在實際工作中，前者的尺度遠比後者要大。因此如果一個指數時間算法的運行時間是前者大小的多項式，那么它仍是可接受的。參數複雜性理論就是要對各種問題澄清是否存在這類算法。而我們的研究工作將會集中於：1。利用參數複雜性和經典複雜性間的同構關係來處理參數複雜性結構理論中的一些未解問題，特別是各種複雜性類的包含關係。2。考察許多組合問題是否存在參數或亞指數近似算法，同時發展相應的PCP理論。3。研究一種常見的設計參數可解算法的方法，即核心化技術，包括尋找許多組合問題的多項式核心算法或證明其不存在。
