计算复杂性类谱图

摘要：

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

关键词：计算复杂性、复杂性类、时间复杂性、空间复杂性

所属期刊栏目：11

分类号：TP301.5(计算技术、计算机技术)

在线出版日期：2015-11-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：40-42