《圖論中NP完全問題的DNA計算》是依託山西大學，由王世英擔任項目負責人的面上項目。
基本介紹
- 中文名：圖論中NP完全問題的DNA計算
- 項目類別：面上項目
- 項目負責人：王世英
- 依託單位：山西大學
- 負責人職稱：教授
- 批准號：60773131
- 研究期限：2008-01-01 至 2008-12-31
- 申請代碼：F0201
- 支持經費：8（萬元）
項目摘要
猜想: 不存在解NP完全問題的多項式時間的算法。它是目前計算機科學和數學最大的未解問題之一。10多年DNA計算機的研究表明，它具有高度的並行性、大容量和低消耗，它在解決圖論或者組合最佳化中的NP完全問題上比電子計算機具有一定的天然優勢。本項目圖論中NP完全問題的DNA計算是計算機科學、數學和生命科學的一個綜合性課題，擬建立具有一定通用性的DNA計算模型，用它解組合最佳化中若干計算問題，如整數線性規劃問題等；擬對DNA計算中的誤差問題和解空間指數爆炸問題進行研究，降低生物運算元目，減少誤差，提高有效解形成的可能，克服解空間指數爆炸問題。擬對新的圖類DNA標號圖進行系統地研究，擴大它的適用範圍，如在DNA計算和測序方面等。進一步研究分子計算系統中有效的生物技術。為用DNA計算機解決組合最最佳化中的計算問題和相關圖論問題的研究打下良好的基礎。
