课程简介：计算复杂性理论是计算机科学中研究各类问题计算复杂性的分支学科，它使用数学方法对计算中所需的各种资源的耗费作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。该课程首先介绍计算复杂性理论的概述、一些计算问题和逻辑，然后详细介绍时间复杂性、NP-完备性、空间复杂性等，最后简单介绍电路复杂性、多项式谱系、随机计算、计数复杂性、扩张图和去随机等。