For a decision problem and a class of Turing machines, we say that if there is a Turing machine bounded by which decides . If is a search problem then if . The most common classes are all restricted to one read-only input tape and one output/work tape (and in some cases a one-way, read-only guess tape) and are defined as follows:
Although is a time complexity class for any , in actual use time complexity classes are usually the union of for many . If is a class of functions then . Most commonly this is used when .
The most important time complexity classes are the polynomial classes:
We say a problem if there is a Turing machine which solves , always halts, and never uses more than cells of its output/work tape. As above, if is a class of function then
The most common space complexity classes are . When this is just called .
If is any complexity class then if is a decision problem and or is a search problem and . Of course, this coincides with the definition of above. Clearly .
Since a machine with a time complexity cannot possibly use more than cells, . If then and similarly for space.
The following are all trivial, following from the fact that some classes of machines accept and reject under stricter circumstances than others: