EASY UNDERSTANDING OF COMPUTATIONAL COMPLEXITY THEORY – A STUDENT’S PERSPECTIVE

Bhalchandra P.U.¹*, More U.L.², Rawangaonkar R.R.³, Tammewar P.R.⁴, Kulkarni P.P.^5
1School of Computational Sciences, Swami Ramanand Teerth Marathwada University, Nanded, 431606, MS, India
²School of Computational Sciences, Swami Ramanand Teerth Marathwada University, Nanded, 431606, MS, India
³School of Computational Sciences, Swami Ramanand Teerth Marathwada University, Nanded, 431606, MS, India
⁴School of Computational Sciences, Swami Ramanand Teerth Marathwada University, Nanded, 431606, MS, India
⁵School of Computational Sciences, Swami Ramanand Teerth Marathwada University, Nanded, 431606, MS, India
* Corresponding Author : pub1976@rediffmail.com

Received : -     Accepted : -     Published : 15-06-2010
Volume : 2     Issue : 1       Pages : 40 - 45
Int J Mach Intell 2.1 (2010):40-45
DOI : http://dx.doi.org/10.9735/0975-2927.2.1.40-45

Keywords : Complexity Theory, P, NP completeness
Conflict of Interest : None declared

Computer Science is largely concerned about a single question - how long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate resulting into formation of computational complexity theory. For entry level students in Data Structures and Analysis of Algorithms, understanding this theory is quite hard as literature review seen so far is dedicated to classifying problems by how hard they are. We have attempted for rigorous analysis of literature review and discovered different types of problems. A division of problem space is suggested in order to put these concepts in simple and conceptually understandable format.

[1] Michael Goodrich (2001) Algorithm Design: Foundations, Analysis, and Internet Examples. Wiley, ISBN-10: 0471383651  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Karam P.A. (2001) Stephen Cook Advances Knowledge of NP-Complete Problems, Assisting Computer Scientists: An entry from Gale's Science and Its Times, Gale  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Garey M.R. and Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979, ISBN-10: 0716710455.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] MichaelT.Goodrich (2002) Algorithm Design, Foundations, Analysis & Internet Examples 2002 publication. John Wiley & Sons, ASIN: B0028IEHY2  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Teofilo F. Gonzalez (2007) NPCompleteness: Theory and Applications. University of California, Santa Barbara  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Frank Hoffmann, David J. Hand, Niall Adams, Douglas Fisher, Gabriela Guimaraes (2001) Advances in Intelligent Data Analysis: 4th International Conference, IDA 2001, Cascais, Portugal, Springer, ISBN-10: 3540425810  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus