计算复杂性理论基础

本书计算复杂性理论是用数学方法研究计算机解决各种算法问题难易程度的理论。本书对这一理论的基础知识做了全面介绍，力争帮助读者掌握该理论的思想方法，为进一步开展计算机科学的相关领域的学习和研究奠定基础。其首先详细介绍计算模型、P v.s.NP问题、归约和NP完备性理论等；然后针对信息安全和算法设计等专业特点，专门详细介绍随机化算法、（非）一致电路；最后简单介绍了几个较深入的课题：交互语言类、计数复杂类、概率可验证语言类等。