The last few weeks in Tech Tuesday we have looked at various aspects of computational complexity. So far whenever we have looked at a sample problem, such as finding words on a web page, we have studied the characteristics of a particular algorithm for solving the problem (in many cases starting out with looking at a brute force solution). But we have skirted the central question of computational complexity: how hard is the problem? Or asked differently, for a given problem, what is the best we can do?
Much of the really hard theoretical work that has gone on in computational complexity centers around assigning problems to complexity classes. A class is defined roughly as:
the set of problems that can be solved by an abstract machine M using O(f(n)) of time or space, where n is the size of the input
where I have linked to the previous posts describing the relevant concepts. The basic idea is that we represent computation by abstract machines (which are analyzable) and then determine how much time or space is required by the best possible solution on that machine. While this is easy to state, finding best solutions and proving that they are best is hard. As we will see in just a second it turns out to harbor one of the great unsolved problems of computer science.
This definition of complexity classes gives rise to a hierarchy which is shown in the following picture (taken from a Penn State class on the theory of computation):
What does this mean? Let’s start at the outermost class of all recognizable problems, also known as decision problems. In our study of the halting problem, we have seen that some problems are simply undecidable. So that’s why in this chart the class of decidable problems is contained strictly inside the class of all problems. This is something we know and has been proven.
Now you see lots more complexity classes nested inside of the decidable problems, such as EXPSPACE, which is the set of all problems decidable by a Turing Machine in O(2^p(n)) tape space where p(n) is a polynomial of n (which is the size of the input). Now the diagram shows this as being strictly larger than EXPTIME, which is the set of problems decidable in exponential time. That, however, so far is only a conjecture. We believe that there are problems that are in EXPSPACE but not in EXPTIME but we don’t have a proof of that.
We do, however, know that EXPSPACE is a strict superset of PSPACE. By now you should be able to guess what the definition of PSPACE looks like: it is the set of problems decidable by a Turing machine in O(p(n)) of space.
Here is something else we know and have already encountered in Tech Tuesday. We saw that the class of regular problems, which can be solved using finite state machines, is strictly smaller than the class CFL, which are the context free languages.
So we have a fair bit of knowledge at the outermost layers of this hierarchy and also at the innermost. But there is a huge gaping hole in the middle where a great many problems reside. In particular you will almost certainly have heard about the question whether or not P = NP. This is considered to be the central unsolved question in computer science. We will take this question up next Tuesday!
PS There are many more complexity classes than are shown in the diagram above. You can find a comprehensive listing in the Complexity Zoo.
