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

• 作者: 徐心和 高强
• 来源期刊: 智能系统学报
• 学科: 工学
• 关键词: 计算复杂性 图灵机 确定型多项式时间复杂性 非确定型多项式时间复杂性 非确定型多项式时间复杂性的完全问题 确定型多项式空间复杂性 确定型多项式空间复杂性的完全问题 可归约性
• 年，卷（期）: 2014,（5）
• 页码范围: 529-535
• 页数: 7页
• 分类号: TP301.5
• 字数: 7690字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-4785.201311055

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐心和	东北大学信息科学与工程学院	295	7536	42.0	73.0
2	高强	东北大学信息科学与工程学院	4	8	2.0	2.0