A set of problems is usually called a class.
It is important to remember that a class of problems is not a class of algorithms.
A decision problem solvable with a fixed amount of memory (by a finite-state machine) is called a finite-state or regular language.
So finite-state machines define the class of all decision problems that can be solved by finite-state machines.
Problems solvable by deterministic Turing-machine algorithms are called computable. That is, deterministic Turing machines define the class of computable problems.
But remember that no Turing machine can be in the class of computable problems, since a Turing machine is not a problem.
All of the problems solved every day by computers are obviously computable. But there are problems that are not computable. Examples are the Halting Problem (shown uncomputable here) and Hilbert's Tenth Problem.
Problems solvable by partial algorithms on Turing machines are called partially computable. Both the Halting Problem and Hilbert's Tenth Problem are partially computable.
There are problems that are so difficult they are not even partially computable. An example is the set of all programs that halt on every input: {p | ∀x(φp(x)↓)}.
We looked at resource-limited computation, focusing on problems computable in polynomial time or polynomial space.
We defined the following complexity classes.
P = the class of all decision problems solvable by deterministic polynomial-time algorithms.
NP = the class of all decision problems solvable by nondeterministic polynomial-time algorithms.
CoNP the class of all complements of problems that are in NP.
PSPACE= the class of all problems solvable by deterministic polynomial-space algorithms.
EXPTIME = the class of all problems solvable by deterministic poly-exponential time algorithms. (An algorithm runs in poly-exponential time if its runs within O(2nk) time for some fixed k.
Known relationships are:
You should be prepared to give a definition of each of the classes mentioned on this page and you should know the relationships that have been stated.