Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a
subscriber to CJTCS. If not,
**please subscribe**
for legitimate access to all journal articles.

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.

- #GA is
*e^(O(sqrt(n log n)))*-enumerable}. - If
*#GA*is polynomially enumerable, then*GI*in R. - For
*epsilon < 1/2*, if #GA is*n^epsilon*-enumerable, then*GI*in P.

- Preformatted versions of the article
- DVI (109,668 bytes)
**PostScript**(508,623 bytes)- PDF (396,240 bytes)
- Audio by
**AsTeR**(to appear)

- Source materials for custom formatting
**LaTeX**(`cj99-01.tex`, 79,371 bytes)**BIBTeX**(`cj99-01.bib`, 9,854 bytes)- Parameter settings for custom
formatting (
`cjropts.tex`, 165 bytes) - Self citation in
**BIBTeX**(311 bytes)

- Online discussion
- Instructions for Readers

DOI: 10.4086/cjtcs.1999.001

Volume 1998, Article 4 Article 2

Volume 1999 Published articles

Volume 1998, Article 4 Article 2

Volume 1999 Published articles

Last modified: Wed Feb 24 15:51:38 CST 1999