On finding the number of graph automorphisms

In computational complexity theory, a function f is called b(n)-enumerable if there exists a polynomial-time function that can restrict the output of f(x) to one of b(n) possible values. This paper investigates #GA, the funct ion that computes the number of automorphisms of an undirected graph, and G I, the set of pairs of isomorphic graphs. The results in this paper show th e following connections between the enumerability of #GA and the computatio nal complexity of GI. 1. #GA is exp(O(root n log n))-enumerable. 2. If #GA is polynomially enumerable, then GI is an element of R. 3. For epsilon < 1/2, if #GA is n(epsilon)-enumerable, then GI is an elemen t of P.