Classifying certain algebraic problems using Logspace counting classes[HBNI Th5]

Abstract

In this thesis the results showing a finer classification of the complexity of several algebraic problems that have efficient polynomial time algorithms are obtained. The problems based on Group theory and Linear Algebra are considered in this thesis. A randomized parallel algorithm to solve LCON and place it in BP.NC^2 is presented in this thesis. A new logspace counting class ModL is introduced and shown that L^ModL = L^GapL. The BP.NC^2 upper bound for LCON also shows LCON is in (L^ModL)/ poly. Some of the well known techniques of polynomial identity testing and the Isolating Lemma are two main ingredients in the results found. Using LCON and LCONX it is also shown that the problem of computing a basis for the nullspace, denoted by LCONNULL, of a mapping in terms of a matrix is also in BP.NC^2 and in L^ModL / poly. A study on generalization of LCON, Testing feasibility of a system of linear equations over a finite ring R having unit element, proves the result that testing feasibility of linear equations over R is also in L^ModL / poly. The matroid intersection problem is considered for linearly representable matroids. It is to find an independent set of maximum cardinality in both M1 and M2. This thesis examines the complexity of problems on groups given by their Cayley as their input. It is shown that many of these problems such as testing whether the input group is simple, nilpotent, solvable, and computing normal closure, centralizer and so on are all logspace computable.