时间复杂性和空间复杂性研究

摘要：

计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性，可以明确该问题是否存在有效的求解算法。介绍并分析了计算理论的一些基本概念，论述了时间复杂性（包括P、NP、NP-hard、NP-complete和EXPTIME）和空间复杂性（包括PSPACE、NPSPACE、PSPACE-hard和PSAPCE-complete）中的各个主要分类。最后分析了各个复杂性类之间的关系。

关键词：计算复杂性、图灵机、确定型多项式时间复杂性、非确定型多项式时间复杂性、非确定型多项式时间复杂性的完全问题、确定型多项式空间复杂性、确定型多项式空间复杂性的完全问题、可归约性

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

资助基金：国家自然科学基金资助项目61370153．

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

页数：共7页

页码：529-535