[1]高强,徐心和.时间复杂性和空间复杂性研究[J].智能系统学报,2014,9(5):529-535.[doi:10.3969/j.issn.1673-4785.201311055]
GAO Qiang,XU Xinhe.Research on time complexity and space complexity[J].CAAI Transactions on Intelligent Systems,2014,9(5):529-535.[doi:10.3969/j.issn.1673-4785.201311055]
点击复制
GAO Qiang,XU Xinhe.Research on time complexity and space complexity[J].CAAI Transactions on Intelligent Systems,2014,9(5):529-535.[doi:10.3969/j.issn.1673-4785.201311055]
时间复杂性和空间复杂性研究
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
9
期数:
2014年第5期
页码:
529-535
栏目:
综述
出版日期:
2014-10-25
- Title:
- Research on time complexity and space complexity
- Keywords:
- computational complexity; Turing machine; P; NP; NP-complete; PSAPCE; PSAPCE-complete; reducibility
- 分类号:
- TP301.5
- 摘要:
- 计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性,可以明确该问题是否存在有效的求解算法。介绍并分析了计算理论的一些基本概念,论述了时间复杂性(包括P、NP、NP-hard、NP-complete和EXPTIME)和空间复杂性(包括PSPACE、NPSPACE、PSPACE-hard和PSAPCE-complete)中的各个主要分类。最后分析了各个复杂性类之间的关系。
- Abstract:
- 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, PSPACE-hard and PSAPCE-complete) by examples. Finally the relations among complexity classes are analyzed.
- 参考文献/References:
-
[1] SIPSER M. Introduction to the theory of computation[M]. 2nd ed. Beijing:China Machine Press, 2006:265-323.
[2] DASGUPTA S, PAPADIMITRIOU C H, VAZI-RANI U V. Algorithm[M]. New York:McGraw-Hill Science/Engineering/Math, 2006:257-264.
[3] PAPADIMITRIOU C. Computational complexity[M]. Reading, Massachusetts:Addison-Wesley, 1994:491-493.
[4] 朱一清.可计算性与计算复杂性[M].北京:国防工业出版社, 2006:44-45.
[5] 堵丁柱.计算复杂性导论[M].北京:高等教育出版社, 2000:21-22.
[6] ARORA S, BARAK B. Computational complexity[M]. New York:Cambridge University Press, 2007:24-85.
[7] 陈志平, 徐宗本.计算机数学——计算复杂性理论与NPC、NP难问题的求解[M].北京:科学出版社, 2001:81-83.
[8] NP[DB/OL].[2013-10-17]. http://zh.wikipedia.or-g/wiki/NP.
[9] COPRIME[DB/OL].[2013-10-17]. http://zh.wikiped-ia.org/wiki/COPRIME.
[10] GRAHAM R L, KNUTH D E, PATASHNIK O. Concrete mathematics[M]. Massachusetts:Addison-Wesley, 1989:107-110.
[11] HONSBERGER R. Mathematical gems II[M]. Washington, DC:The Mathematical Association of America, 1976:54-57.
[12] KARP R M. Reducibility among combinatorial problems[Z]. New York:Plenum Press, 1972:85-103.
[13] COOK S A. The complexity of theorem proving procedures[C]//Proceedings of the Third Annual ACM Symposium on Theory of Computing. New York, USA, 1971:151-158.
[14] ZHANG Lintao. Searching for truth:techniques for satisfiability of boolean formulas[D]. Princeton:Princeton University, 2003:10-14.
[15] CORMEN T H, LEISERSON C H, RIVEST R L, et al. Introduction to algorithms[M]. 2nd ed. Cambridge, Massachusetts:MIT Press, 2009:1108-1110.
[16] VERTEX COVER[DB/OL].[2013-10-19]. http://zh.wikipedia.org/wiki/VERTEXCOVER.
[17] STOCKMEYER L J, CHANDRA A K. Provably difficult combinatorial games[J]. SIAM J Compuf, 1979 8(2):151-174.
[18] 罗森.离散数学及其应用[M].北京:机械工业出版社, 2011:21-30.
[19] PSPACE[DB/OL].[2013-10-20].http://zh.wikipedia.org/wiki/PSPACE.
[20] SAVITCH W J. Relationships between nondeterministic and deterministic tape complexities[J]. Journal of Computer and System Sciences, 1970 4(2):177-192.
- 相似文献/References:
-
[1]何华灿,何智涛.无穷概念的重新统一[J].智能系统学报,2010,5(3):202.
HE Hua-can,HE Zhi-tao.Reunifying concepts of infinity[J].CAAI Transactions on Intelligent Systems,2010,5():202.
[2]李微,乔俊飞,韩红桂,等.模糊规则相似性计算与性能分析研究[J].智能系统学报,2017,12(1):124.[doi:10.11992/tis.201512040]
LI Wei,QIAO Junfei,HAN Honggui,et al.Computing and performance analysis of similarity between fuzzy rules[J].CAAI Transactions on Intelligent Systems,2017,12():124.[doi:10.11992/tis.201512040]
备注/Memo
收稿日期:2013-11-22。
基金项目:国家自然科学基金资助项目(61370153).
作者简介:徐心和, 男, 1940年生, 教授, 博士生导师, 中国人工智能学会常务理事, 主要研究方向为控制理论与应用、系统仿真、智能机器人、机器博弈等, 主持完成国家自然科学基金项目、863基金项目、国家"八五"、"九五"攻关课题13项, 其中8项通过省、部级鉴定, 获科技进步奖国家三等1项, 省部级科技进步奖多项。发表学术论文300余篇。
通讯作者:高强, 男, 1980年生, 讲师, 博士研究生, 主要研究方向为机器博弈、计算复杂性理论。E-mail:tommy_06@163.com.
更新日期/Last Update:
1900-01-01