共 3 条
- [1] 离散数学及其应用.[M].(美) 罗森 (Rosen;K.H.) ; 著.机械工业出版社.2011,
- [2] 计算复杂性导论.[M].堵丁柱等[著];.高等教育出版社.2002,
- [3] 计算机数学.[M].陈志平;徐宗本编著;.科学出版社.2001,
时间复杂性和空间复杂性研究
被引：4
作者：
高强
徐心和
机构：
[1] 东北大学信息科学与工程学院
来源：
关键词：
计算复杂性;
图灵机;
确定型多项式时间复杂性;
非确定型多项式时间复杂性;
非确定型多项式时间复杂性的完全问题;
确定型多项式空间复杂性;
确定型多项式空间复杂性的完全问题;
可归约性;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性,可以明确该问题是否存在有效的求解算法。介绍并分析了计算理论的一些基本概念,论述了时间复杂性(包括P、NP、NP-hard、NP-complete和EXPTIME)和空间复杂性(包括PSPACE、NPSPACE、PSPACE-hard和PSAPCE-complete)中的各个主要分类。最后分析了各个复杂性类之间的关系。
引用
收藏
页码：529 / 535
页数：7
相关论文