摘要
计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性,可以明确该问题是否存在有效的求解算法。介绍并分析了计算理论的一些基本概念,论述了时间复杂性(包括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.
出处
《智能系统学报》
CSCD
北大核心
2014年第5期529-535,共7页
CAAI Transactions on Intelligent Systems
基金
国家自然科学基金资助项目(61370153)
