Few technical terms have gained such rapid notoriety as the appela- tion HNP-complete." In the short time since its introduction in the early 1970's, this term has come to symbolize the abyss of inherent intractability that algorithm designers increasingly face as they seek to solve larger and more complex problems. A wide variety of commonly encountered prob- lems from mathematics, computer science, and operations research are now known to be NP-complete, and the collection of such problems continues to grow almost daily. Indeed, the NP-complete problems are now so pervasive that it is important for anyone concerned with the computational aspects of these fields to be familiar with the meaning and implications of this concept.

计算复杂性理论经典教材，Garey&Johnson

书名：Computer And Intractability：A Guide To The Theory Of NP-Completeness PDF格式 来源：网络

在计算机科学中，更具体地说是计算复杂性理论，《计算机和难以理解：NP完全性理论指南》是Michael Garey和David S. Johnson的有影响力的教科书。这是第一本专门讨论NP完全性和计算难处理性的书。本书的附录提供了NP完全问题的全面概要（在本书的后续印刷中进行了更新）。 这本书现在在某些方面已经过时，因为它没有涉及最近的发展，例如PCP定理。 尽管如此，它仍然是印刷品并且被认为是经典之作：在2006年的一项研究中，CiteSeer搜索引擎将该书列为计算机科学文献中被引用最多的参考书。

Computers and intractability a guide to the theory of np-completeness.pdf

Computers And Intractability A Guide To The Theory Of Np Completeness. PDF版

介绍NPC的经典书籍，根据清晰扫描版进行进行裁剪、排版，更加适合阅读和打印。