第2章 圖與計(jì)算復(fù)雜性
第1章指出：NP完全問題是阻礙當(dāng)今科技發(fā)展的“絆腳石”。由于DNA計(jì)算的并行性對求解NP完全問題有天然的優(yōu)勢，故數(shù)十年來DNA計(jì)算的研究主要集中于求解NP完全問題?？紤]到許多NP完全問題是圖論問題，本章首先介紹圖論的一些基本知識，然后逐步揭曉NP完全問題的“廬山真面目”，介紹NP完全問題的相關(guān)理論，特別是計(jì)算復(fù)雜性。
推薦閱讀
第1章指出：NP完全問題是阻礙當(dāng)今科技發(fā)展的“絆腳石”。由于DNA計(jì)算的并行性對求解NP完全問題有天然的優(yōu)勢，故數(shù)十年來DNA計(jì)算的研究主要集中于求解NP完全問題?？紤]到許多NP完全問題是圖論問題，本章首先介紹圖論的一些基本知識，然后逐步揭曉NP完全問題的“廬山真面目”，介紹NP完全問題的相關(guān)理論，特別是計(jì)算復(fù)雜性。