Explore the World of Scientific Modeling and Simulation


Computational Complexity Theory


Computational complexity theory analyzes the resources required to solve computational problems within defined computational models and resource measures. To analyze theoretical solvability, theorists construct Turing machines, Boolean Circuits, Parallel Random Access Machines and other abstract computational tools that are assigned limits on resources including space, time and hardware.

In complexity theory, a set of problems that can be solved in a particular model within particular resource limits is called a complexity class. The chart below shows the relationships of complexity classes.

Chart: University of Massechusetts Department of Computer Science