One of the goals of complexity theory is the classification of problems in complexity classes; these classes include problems which can be solved using some specific amounts of a resource.

We have interest in the parallel complexity of problems and their classification in complexity classes. One of the main motivations is that parallel hardware is readily available, but it is not clear how to characterize problems that can be solved more efficiently in parallel than serially.

In spite of many results in the area, a question of interest is: what polynomial time problems can be solved in polylogarithmic time using a polynomial number of processors?, or more generally, what problems have a parallel solution which improves substantially upon their serial solution?

* Revised: 2006.1.1*