Counting complexity and computational group theory

Abstract

The main contribution of this thesis is in proving upper bounds on the counting complexity of some computational problems that arise from group theory. It consists of two parts. The first part concentrates on studying the complexity of three basic, computationally hard, group-theoretic problems over black-box groups. These problems are membership testing, Order verification, and Isomorphism testing. It is shown that all these problems over solvable black-box groups are in the complexity class SPP. The second part of the thesis focus on studying the complexity of various representation classes with respect to their learnability, in particular the learnability of some group theoretic and linear algebraic concept classes. The complexity of learning these algebraic concept classes is compared to that of learning boolean functions represented in conjunctive normal form. A refinement of Angluin's model called the teaching assistant model of exact learning is proposed in order to do a finer classification of the complexity of exact learning. It acts as an interface between the teacher and the learner. The notion of teaching assistant classes are defined in exact analogy with known complexity classes; As one of the main results it is shown that while permutation groups (Linear spaces over fixed finite fields) can be learned using a teaching assistant in the assistant class analogous to LWPP (respectively, SPP), it is unlikely that the class 3-CNF can be learned using an LWPP or SPP assistant. The power of various assistant classes are investigated and representation classes which separate these assistant classes are exhibited. The two parts of the thesis are addressing two different issues but there are some underlying connections between the two parts. In both the parts the issue of analyzing the complexity of some computational problems over finite groups, although the exact nature of the problems differ. The learning algorithms designed with LWPP and SPP teaching asssistants are built on the complexity theoretic ideas used in showing the upper bound results in the first part of the thesis.