Computational complexity theory (often just called "complexity theory" when there is no possibility of confusion with the Santa Fe Institute variety) is the study of how hard it is to solve different kinds of computational problems. Since we generally don't know how hard it is to solve these problems, complexity theorists spend most of their time categorizing the problems into groups of problems that are all equally hard in some sense, even if we don't necessarily know how hard that is. The hope is that eventually we can put some labels on the boxes that tell us how hard the contents are, and in the meantime we can at least say that all the problems in that NP-complete box over there look mighty damned hard.
1. Decision problems and languages
In order to compare the difficulty of different problems, it helps to shoehorn them all into a single framework. So most problems studied in complexity theory have been bent until they look like decision problems, for which the output is always yes or no (sometimes called accept or reject). Mathematically, a decision problem can be represented by the set of inputs for which the output is "yes"; these are called the accepting instances of the problem and are encoded as strings of characters over some alphabet. A set of strings of characters is called a language, and a the set of languages that all satisfy some criterion for hardness is called a complexity class.
For example, the decision problem "Is the string w a palindrome over the alphabet {a,b}?" is represented by the (infinite) language L = { a, b, aa, bb, aaa, aba, bab, bbb, aaaa, abba, baab, ... }.
2. Complexity classes
The palindrome language L above is in the complexity class P of all polynomial-time solvable problems, because there is an O(nc) (specifically, O(n)) time algorithm that tests for any w whether w is or is not in L. Formally:
P = { L : there exists an O(nc) time algorithm, for some constant c, that tests membership in L }. (Polynomial time.)
Here are some more complexity classes:
EXPTIME = { L : there exists an algorithm that tests membership in L in O(2p(n)) time, where p(n) = O(n^c) for some constant c }. (Exponential time.)
PSPACE = { L : there exists an algorithm that tests membership in L that uses O(nc) space }. (Polynomial space.)
It is known that there are problems that are in EXPTIME but not in P (an example is "Does black win a game of Go played on an nxn board with optimal play starting in this position?"). It is not known whether there are any problems in PSPACE that are not in P.
The most famous complexity class other than P is its seemingly more powerful variant NP. For a definition, see PvsNp. For many more complexity classes, see Computational_complexity_theory.