论文部分内容阅读
一个问题的计算复杂性(complexity)是指用计算机解决它的复杂程度,其度量标准:一是计算所需的步数或指令条数(即时间复杂度),二是计算所需的存储单元数(即空间复杂度)。复杂度相似的所有问题构成的集合就是一个复杂性类(complexity class)。该文探讨了在计算复杂性理论中常见的几种比较重要的计算复杂性类,研究了对计算复杂性归类的重要意义,以及复杂性类之间的一些关联。