計算機和難解性

內容介紹

本書系統地介紹了NP完全性理論的概念和方法，全書共分為7章和兩個附錄。第一章粗略地介紹了計算複雜性的一些基本概念和NP完全性理論的意義。第二章至第五章介紹了NP完全性的基本理論和證明的方法。第六章集中研究NP難問題的近似算法。第七章概述了大量計算複雜性中的有關理論課題。 附錄A收集了範圍廣泛、內容豐富的NP完全性和NP難的問題、附錄B補充了NP問題的一些最新的進展，既有理論方面的，又有關於具體問題的。