III.10 Computational Complexity Classes
One of the basic challenges of theoretical computer science is to determine what computational resources are necessary in order to perform a given computational task. The most basic resource is time, or equivalently (given the hardware) the number of steps needed to implement the most efficient algorithm that will carry out the task. Especially important is how this time scales up with the size of the input for the task: for instance, how much longer does it take to factorize an integer with 2n digits than an integer with n digits? Another resource connected with the feasibility of a computation is memory one can ask how much storage space a computer will need in order to implement an algorithm, and how this can be minimized A complexity class is a set of computational problems that can be performed with certain restrictions on the resources allowed. For instance, the complexity class P consists of all problems that can be performed in “polynomial time”: that is, there is some positive integer k such that if the size of the problem is n (in the example above, the size was the number of digits of the integer to be factorized), then the computation can be carried out in at most nk steps. A problem belongs to P if and only if the time taken to solve it scales up by at most a constant factor when the size of the input scales up by a constant factor. A good example of such a problem is multiplication of two n-digit numbers: if you use ordinary long multiplication, then replacing n by 2n increases the time taken by a factor of 4.
Suppose that you are presented with a positive integer x and told that it is a product of two primes p and q. How difficult is it to determine p and q? Nobody knows, but one thing is easy to see: if you are told p and q, then it is not hard (for a computer, at any rate) to check that pq really does equal x. Indeed, as we have just seen, long multiplication takes polynomial time, and comparing the answer with x is even easier. The complexity class NP consists of those computational tasks for which a correct answer can be verified in polynomial time, even if it cannot necessarily be found in polynomial time. Remarkably, although this is a fundamental distinction, nobody knows how to prove that P 
NP: this problem is widely considered to be the most important in theoretical computer science.
We briefly mention two other important complexity classes. PSPACE consists of all problems that can be solved using an amount of memory that grows at most polynomially with the size of the input. It turns out to be the natural class associated with reasonable computational strategies for games such as chess. The complexity class NC is the set of all Boolean functions that can be computed by a “circuit of polynomial size and depth at most a polynomial in log n.” This last class is a model for the class of problems that can be solved very rapidly using parallel processing. In general, complexity classes are often surprisingly good at characterizing large families of problems with interesting and intuitively recognizable features in common. Another remarkable fact is that almost all complexity classes have “hardest problems” within them: that is, problems for which a solution can be converted into a solution for any other problem in the class. These problems are said to be complete for the class in question.
These issues, as well as several other complexity classes, are discussed in COMPUTATIONAL COMPLEXITY [IV.20]. A vast number of further classes can be found at
http://qwiki.stanford.edu/wiki/Complexity_Zoo
along with a brief definition of each.