Complexity Theory

Introduction Computational complexity is the study of the di#culty 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 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 are P, the set of problems that can be solved in polynomial time, and NP, the set of problems whose solutions can be verified in polynomial time. By quantifying the resources required to solve a problem, complexity theory has profoundly a#ected our thinking about computation. Computability theory establishes the existence of undecidable problems, which cannot be solved in principle regardless of the amount of time invested. However, computability theor