T007520 NPC理论导引
张泽增著。 贵州人民出版社1989年3月版。15．8万字。 主要介绍计算复杂度理论入门知识——NPC理论的基础概念和基础理论。 分5章，第一章主要介绍问题的难易性和复杂度的有关概念，其中图灵机和基于图灵机的复杂度概念，是全书的基础；第二章介绍证明NPC类的方法，主要有限制法、局部替换法与分量设计法；第三章讨论P类与NPC类的分界，并通过举例来讲述证明问题属于P类的方法；第四章讨论对付NPC问题的办法，简要介绍近似算法、概率算法与并行算法；第五章介绍NPC类的结构及进一步的知识，包括CO－NP，强NPC，PSPACE，NPC的相对化等。 为“计算机科学丛书”之一。 |