Complexity upper bounds using permutation group theory

Abstract

This thesis studies the Graph Isomorphism and problems that arise in Galois theory. It is targeted to use structural properties of permutation groups together with other algebraic techniques to prove complexity upper bounds. Complexity theory is the study of resource bounded computations. Efficiency is measured in terms of the resource required to solve the problem as a function of the input size. The study of complexity Graph Isomorphism and problems associated with Galois theory with an aim of classifying these in the frame work of complexity theory is undertaken. The role of permutation group theory is a common thread that connects these two. The structure of permutation groups and the numerous efficient algorithms for permutation group problems play an important role in this thesis results. Permutation groups also plays an important role in algorithms for Graph Isomorphism. Group theory has played an important role in various complexity theoretic results. Chapter 2 speaks about a brief survey of the complexity theory required for this thesis; Chapter 3 develops the required group theory. Chapter 6 describes the required algebraic number theory, from which some of the results leads to one of the results on Galois theory in this thesis. Chapters 4 and 5 explains the results on Graph Isomorphism and related problems. The results on computational problems in Galois theory is described in Chapters 7,8 and 9.