kk '''Complexity Theory''' is a 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 does it take to solve a problem) and ''space'' (how much memory does it take to solve a problem). 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.
A single "problem" is an entire set of related questions, where each question is a finite-length [[string]]. For example, the problem [[Integer factorization|''FACTORIZE'']] is: given an integer written in binary, return all of the [[prime number|prime]] factors of that number. A particular question is called an ''instance''. For example, "give the factors of the number 15" is one instance of the ''FACTORIZE'' problem.
