Computational complexity of many natural algorithmic problems are, in a sense, nicely understood. Either they have efficient (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.
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 and Isomorphism Testing. These are computational problems for which no polynomial-time algorithms exist. We show that these problems, over solvable black-box groups, are in the counting class SPP. The proof of this result is built on a constructive version of the fundamental theorem of finite abelian groups. The class SPP is known to be low for many counting classes. Since it is unlikely that the class NP is low for these counting classes, these upper bounds give evidence that these problems are unlikely to be hard for NP.
In the second part of the thesis we study the problem of computing a generator set of an unknown group, given a membership testing oracle for the group. Because of the close relation of this problem with concept learning, we study this problem in the framework of learning theory. In Chapter 5, for analyzing the complexity of learning, we introduce a new model of exact learning called the teaching assistant model. This model can be seen as an enhancement of Angluin's exact learning model. The main ingredient of this model is the notion of a teaching assistant which acts as an intermediate agent between the learner and the teacher. This leads to a notion of teaching assistant classes which are analogous to complexity classes. The teaching assistant classes of main interest to us are the ones analogous to the counting complexity classes SPP and LWPP. In Chapter 5, after giving detailed definitions of all the notions involved in this model, we study the complexity of learning three representation classes in this model. These are the classes SYM of permutation groups, LIN(p) of linear spaces over the finite field of size p and the class 3-CNF of boolean functions represented in conjunctive normal form where each clause has at most three literals. We show that the class SYM is learnable with an LWPP-assistant and LIN(p) is learnable with an SPP-assistant. On the other hand, we also show that 3-CNF is not learnable with an SPP-assistant (LWPP-assistant) unless NP is contained in SPP (respectively, LWPP). These containments are unlikely. Motivated by these results, in Chapter 6 we define more assistant classes and prove absolute separations among these assistant classes. For separating various assistant classes we use some natural subclasses of the representation class SYM.
1. Introduction. 2. Preliminaries. 3. Computational Group Theory. 4. Solvable Black-box Group Problems. 5. Exact Learning via Teaching Assistants. 6. Separating Teaching Assistant Classes. 7. Conclusions. Bibliography and Appendix.
