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