Chennai, INDIA, 1999

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.