Counting complexity and computational group theory
N. V. Vinodchandran · 1998
The study of counting complexity classes has been a very fruitful and promising area in complexity theory. This study has given important insights into the inherent complexity of many natural computational problems. Problems arising from group theory have been studied by many researchers. These problems are interesting from the complexity-theoretic viewpoint since the complexity status of many of these problems is not settled. In this dissertation, we study some problems from group theory in the context of counting complexity. More specifically, we place some basic computational grouptheoretic problems in counting classes of low complexity. These results help in giving further insights into the intriguing nature of the complexity of these problems. This thesis consists of two parts. In Chapter 4, which comprises the first part, we study the complexity of three basic computational group-theoretic problems over black-box groups. The problems are Membership Testing, Order Verification a...