Computational complexity theory

Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes). Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.

Related Topics:
Theory of computation - Parallel processor - Computability theory

~ ~ ~ ~ ~ ~ ~ ~ ~ ~