[1]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]
Copy

Research on time complexity and space complexity

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 9 Number of periods: 2014 5 Page number: 529-535 Column: 综述 Public date: 2014-10-25
Title:
Research on time complexity and space complexity
Author(s):
GAO Qiang;  XU Xinhe
College of Information Science and Engineering, Northeastern University, Shenyang 110004, China
Keywords:
computational complexity; Turing machine; P; NP; NP-complete; PSAPCE; PSAPCE-complete; reducibility
CLC:
TP301.5
DOI:
10.3969/j.issn.1673-4785.201311055
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems