On Finding the Number of Graph Automorphisms.
Robert Beals, Richard Chang, William I. Gasarch, Jacobo Torán · 1999
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 function that computes the number of automorphisms of an undirected graph, and GI, the set of pairs of isomorphic graphs. The results in this paper show the following connections between the enumerability of #GA and the computational complexity of GI. 1. #GA is exp(O( # n log n))-enumerable. 2. If #GA is polynomially enumerable, then GI # R. 3. For # < 1 2 , if #GA is n # -enumerable, then GI # P.