Complexity Theory

Authored by: Allender* Eric W. , Loui Michael C. , Regan Kenneth W.

Computing Handbook

Print publication date:  May  2014
Online publication date:  May  2014

Print ISBN: 9781439898529
eBook ISBN: 9781439898536
Adobe ISBN:

10.1201/b16812-10

 Download Chapter

 

Abstract

Computational complexity is the study of the difficulty of solving computational problems, in terms of the required computational resources, such as time and space (memory). Whereas the analysis of algorithms focuses on the time or space requirements of an individual algorithm for a specific problem (such as sorting), complexity theory focuses on the complexity class of problems solvable in the same amount of time or space. Most common computational problems fall into a small number of complexity classes. Two important complexity classes areP, the set of problems that can be solved in polynomial time, andNP, the set of problems whose solutions can be verified in polynomial time.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.