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

Research on time complexity and space complexity

作　　者：高强[1] 徐心和[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《智能系统学报》2014年第5期529-535,共7页CAAI Transactions on Intelligent Systems

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

摘　　要：计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性,可以明确该问题是否存在有效的求解算法。介绍并分析了计算理论的一些基本概念,论述了时间复杂性(包括P、NP、NP-hard、NP-complete和EXPTIME)和空间复杂性(包括PSPACE、NPSPACE、PSPACE-hard和PSAPCE-complete)中的各个主要分类。最后分析了各个复杂性类之间的关系。Computational complexity is used to measure the level of difficulty of a problem being solved. The research on computational complexity of the problem can make it explicit. This paper introduces and analyzes some fundamental concepts of the computation theory and discusses some main classes of time complexity（ including P,NP,NP-hard,NP-complete and EXPTIME） and space complexity（ including PSPACE,NPSPACE,PSPACEhard and PSAPCE-complete） by examples. Finally the relations among complexity classes are analyzed.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]