Counting Complexity and Computational Group Theory
Computational complexity of many natural algorithmic problems are, in a sense, nicely understood. Either they have efficiant (polynomial time) solutions or they are shown to be complete for some natural complexity class. But, many computational problems arising from group theory defy such classification. On the one hand, the exponential size of their solution space prevents them from having polynomial time algorithms. On the other hand the inherent structure in them makes reductions to these problems difficult. In this thesis, we try to understand the complexity of many group theoretic problems by investigating their counting complexity.
For those who are interested to know more about it, you can get either the whole thesis or the relevent chapters (all ps files). Here you can find the Abstract . Check out the Contents before downloading the required chapters. Here is a very brief introduction to some aspects of Computational Group Theory. (Chapter 3 of the thesis).