% The Chicago Journal of Theoretical Computer Science, Volume 1999, Article 1 % Published by MIT Press, Cambridge, Massachusetts USA % Copyright 1999 by Massachusetts Institute of Technology % \newtoks\rstyle \rstyle={cjlook} % \documentclass[v1.1,published]{cjstruct} % % Local style resources for this article. % \usestyleresource{amstext} \usepackage{epic} \usepackage{eepic} \usepackage{amsfonts} \usepackage{amssymb} % % Local macro definitions for this article. % \catcode`\@=11 \ifx\nopagebreakbeginpar\undeftex \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000} \fi \ifx\nopagebreakendpar\undeftex \newcommand{\nopagebreakendpar}{\@endparpenalty10000} \fi \ifx\nopagebreakinteritem\undeftex \newcommand{\nopagebreakinteritem}{\@itempenalty10000} \fi \catcode`\@=12 % \newcommand{\prooffontshape}{\fontshape{n}\selectfont} % \newcommand{\setof}[2]{\left\{\,#1:#2\,\right\}} \tolerance=9000 \newcommand{\myBbb}{\mathbb} \newcommand{\nat}{\mbox{\(\myBbb N\)}} \newcommand{\mytwlrm}{\normalsize\rm} \newcommand{\myninrm}{\small\rm} \newcommand{\ang}[1]{\langle#1\rangle} \newcommand{\implies}{\Rightarrow} \newcommand{\iso}{\simeq} \renewcommand{\iff}{\Longleftrightarrow} \newcommand{\compose}{\mbox{\(\stackrel{\circ}{\rule{0ex}{0ex}}\)}} \renewcommand{\P}{{\rm P}} \newcommand{\PF}{{\rm PF}} \newcommand{\PFq}[2]{\PF^{#2[#1]}} \newcommand{\R}{{\rm R}} \newcommand{\NP}{{\rm NP}} \newcommand{\coNP}{\mbox{{\rm co-NP}}} \newcommand{\PH}{{\rm PH}} \newcommand{\PP}{{\rm PP}} \newcommand{\SAT}{{\rm SAT}} \newcommand{\sSAT}{{\rm \#SAT}} \newcommand{\ga}{{\rm GA}} \newcommand{\gi}{{\rm GI}} \newcommand{\sga}{\#{\rm GA}} \newcommand{\sgi}{\#{\rm GI}} \newcommand{\pleq}[1]{\leq_{#1}^{\rm p}} \newcommand{\m}{{\rm m}} \newcommand{\pml}{\pleq{\m}} \newcommand{\C}{{\cal C}} \newcommand{\eF}{\mbox{\({\cal F}\)}} \newcommand{\Qlist}{\mbox{\({\cal Q}\)}} \newcommand{\bvec}{{\vec b}} \newcommand{\bitq}{\{0,1\}^{q(n)}} \newcommand{\Char}[1]{\chi^{#1}} \newcommand{\CharGI}{\mbox{\(\Char{\gi}\)}} \newcommand{\POSS}{\mbox{{\rm POSS}}} \newcommand{\GXqn}{(G,X_1), \ldots, (G, X_{q(n)})} \newcommand{\GHq}{\mbox{\((G_{1},H_{1}),\dots,(G_{q},H_{q})\)}} \def\registered{\({}^{\ooalign% {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}% \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)} % % end of local macro definitions for this article % \begin{document} % \begin{articleinfo} % \publisher{The MIT Press} % \publishercomment{% {\Large \begin{center} Volume 1999, Article 1\\ \textit{On Finding the Number of Graph Automorphisms} \end{center} } \par\noindent ISSN 1073--0486\@. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; \emph{journals-orders@mit.edu, journals-info@mit.edu}\@. Published one article at a time in \LaTeX\ source form on the Internet\@. Pagination varies from copy to copy\@. For more information and other articles see: \begin{itemize} \item \emph{http://mitpress.mit.edu/CJTCS/} \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/} \item \emph{ftp://mitpress.mit.edu/pub/CJTCS} \item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs} \end{itemize} \sentence \par\noindent The \emph{Chicago Journal of Theoretical Computer Science} is abstracted or indexed in \emph{Research Alert,\registered SciSearch,\registered Current Contents\registered/Engineering Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered} } % \copyrightstmt{% \copyright 1999 The Massachusetts Institute of Technology\@. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to ensure fair attribution to authors and the journal, and to prohibit use in a competing commercial product\@. See the journal's World Wide Web site for further details\@. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; \emph{journals-rights@mit.edu}\@.\pagebreak[2] } % \journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science} \journalcomment{% The \emph{Chicago Journal of Theoretical Computer Science} is a peer-reviewed scholarly journal in theoretical computer science\@. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science\@. \par \begin{trivlist} \item[\emph{Editor-in-Chief:}] Janos Simon \item[\emph{Consulting Editors:}] Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel \item[\emph{Editors:}] \begin{tabular}[t]{lll} Martin Abadi & Greg Frederickson & John Mitchell \\ Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\ Eric Allender & Georg Gottlob & Gil Neiger \\ Tetsuo Asano & Vassos Hadzilacos & David Peleg \\ Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\ Eric Bach & Maurice Herlihy & James Royer \\ Stephen Brookes & Ted Herman & Alan Selman \\ Jin-Yi Cai & Stephen Homer & Nir Shavit \\ Anne Condon & Neil Immerman & Eva Tardos \\ Cynthia Dwork & Howard Karloff & Sam Toueg \\ David Eppstein & Philip Klein & Moshe Vardi \\ Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\ Lance Fortnow & Stephen Mahaney & Pierre Wolper \\ Steven Fortune & Michael Merritt \end{tabular} \vspace{1ex} \item[\emph{Managing Editor:}] Michael J.\ O'Donnell \vspace{1ex} \item[\emph{Electronic Mail:}] \emph{chicago-journal@cs.uchicago.edu} \end{trivlist} \sentence } % \bannerfile{cjtcs-banner.tex} % \volume{1999} % \articleid{1} % \selfcitation{ @article{cj99-01, author={Robert Beals and Richard Chang and William Gasarch and Jacobo Tor\'an\/}, title={On Finding the Number of Graph Automorphisms}, journal={Chicago Journal of Theoretical Computer Science}, volume={1999}, number={1}, publisher={MIT Press}, month={February}, year={1999} } } % \begin{retrievalinfo} \end{retrievalinfo} % \title{On Finding the Number of Graph Automorphisms} \shorttitle{Number of Graph Automorphisms} % \editorname{} % % \begin{authorinfo} % % Correction to error in cjstruct.sty version 1.1. % \def\fixversion{1.1} \ifx\cjversion\fixversion \renewcommand{\printname}[1]{ \global\authorstring={#1} \global\authorstrue \ifinfo\item Printed name: #1\fi } \fi % % End of correction. % \printname{Robert Beals} \collname{}{Beals, Robert} \begin{institutioninfo} \instname{University of Arizona} \department{Department of Computer Science and Department of Mathematics} \address{}{Tuczon}{AZ}{85712}{USA} \end{institutioninfo} \email{beals@math.arizona.edu} \end{authorinfo} % \begin{authorinfo} \printname{Richard Chang} \collname{}{Chang, Richard} \begin{institutioninfo} \instname{University of Maryland Baltimore County} \department{Department of Computer Science and Electrical Engineering} \address{}{Baltimore}{MD}{USA}{21250} \end{institutioninfo} \email{chang@umbc.edu} \end{authorinfo} % \begin{authorinfo} \printname{William Gasarch} \collname{}{Gasarch, William} \begin{institutioninfo} \instname{University of Maryland College Park} \department{University of Maryland Institute for Advanced Computer Studies and Department of Computer Science} \address{}{College Park}{MD}{USA}{20742} \end{institutioninfo} \email{gasarch@cs.umd.edu} \end{authorinfo} % \begin{authorinfo} \printname{Jacobo Tor\'an\/} \collname{}{Tor\'an\/, Jacobo} \begin{institutioninfo} \instname{University of Ulm} \department{Theoretische Informatik} \address{}{}{D-99069 Ulm}{Germany}{} \end{institutioninfo} \email{toran@informatik.uni-ulm.de} \end{authorinfo} % \shortauthors{Beals et al.} % \support{ Dr. Beals's work was supported in part by an NSF Mathematical Sciences Postdoctoral Fellowship and by the Alfred P.~Sloan Foundation. {Dr. Chang}'s work was supported in part by National Science Foundation grants CCR-9309137 and CCR-9610457, and by the University of Maryland Institute for Advanced Computer Studies. Dr. Gasarch's work was supported in part by National Science Foundation grant CCR-9301339. Dr. Tor\'an's work was done while he was at Dept.\ Llenguatges i Sistemes Inform\`atics, Universitat Polit\`ecnica de Catalunya, Pau Gargallo 5, E-08028 Barcelona, Spain, and was supported in part by the European Community through the Espirit BRA Program (project 7141, ALCOM II). } % \begin{editinfo} %\date{March 5, 1997} % revised version submitted to CJTCS %\date{November 14, 1997} % re-revised version submitted to CJTCS \submitted{05}{04}{1997}\submitted{14}{11}{1997}\reported{1}{7}{l998}\published{10}{02}{1999} \end{editinfo} % \end{articleinfo} % \begin{articletext} \begin{abstract} % In computational complexity theory, a function \(f\) is called \(b(n)\textrm{-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 \(\sga\), 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 \(\sga\) and the computational complexity of \gi\@. \begin{enumerate} \item \(\sga\) is \(\exp(O(\sqrt{n \log n}))\textrm{-enumerable}\)\@. \item If \(\sga\) is polynomially enumerable, then \(\gi\in\R\)\@. \item For \(\epsilon < {1 \over 2}\), if \(\sga\) is \(n^\epsilon\textrm{-enumerable,}\) then \(\gi\in\P\)\@. \end{enumerate} \end{abstract} \asection{1}{Introduction} % \apar{1-1} The Graph Isomorphism (GI) problem has a special place in computational complexity theory\@. The set \gi\ consists of all pairs of graphs that are isomorphic to each other\@. \gi\ is known to be in \NP\ but not \NP-complete unless the Polynomial Hierarchy collapses \cite{cj99-01-15,cj99-01-30}, a condition that violates the usual intractability assumptions\@. Nevertheless, there is no known polynomial-time algorithm to solve the isomorphism problem on general graphs even though some progress has been made towards polynomial-time algorithms in special cases (most notably for planar graphs~\cite{cj99-01-18,cj99-01-19}, graphs of bounded genus~\cite{cj99-01-14,cj99-01-25}, bounded-degree graphs~\cite{cj99-01-23}, and graphs with bounded eigenvalue multiplicities~\cite{cj99-01-02})\@. Thus, the Graph Isomorphism problem belongs to a short list of problems in \NP\ that are suspected to be neither decidable in polynomial time nor \NP-complete\@. In fact, the exact complexity of \gi\ remains an open problem\@. For example, it is not known whether \gi\ can be solved in randomized polynomial time or whether \gi\ is contained in the class \(\NP \cap \coNP\)\@. % \apar{1-2} The current state of knowledge on the complexity of \gi\ depends on the two-round interactive protocol for Graph Non-Isomorphism \cite{cj99-01-15}, a technique that we exploit in this paper\@. However, even before this proof was discovered, it was suspected that \gi\ could not be \NP-complete because counting the number of graph isomorphisms has roughly the same complexity as deciding the existence of an isomorphism \cite{cj99-01-24}\@. In contrast, the counting versions of typical \NP-complete problems tend to be much harder than the decision versions\@. The proof that counting graph isomorphisms is relatively ``easy'' also demonstrated a close connection between the structure of graph isomorphisms and graph automorphisms (isomorphisms between a graph and itself)\@. The results in this paper add another link to this connection\@. % \apar{1-3} In computational complexity theory, a function is called \(b(n)\textrm{-enumerable}\)\footnote{Not to be confused with recursive enumerability in recursive function theory or countable (denumerable) sets in set theory\@.} if a polynomial-time function can determine a restricted range for the function\@. For example, \emph{a priori\/} the \sga\ function, which computes the number of automorphisms in a graph, may output any value from 1 to \(n!\) for a graph with \(n\) vertices\@. However, we will show that \sga\ can take on only one of \(\exp(O(\sqrt{n \log n}))\) values --- i.e., we will show that \sga\ is \(\exp(O(\sqrt{n \log n}))\textrm{-enumerable}\)\@. The other main results in this paper show that if \sga\ is ``easy'' in the sense of enumerability, then there is a corresponding decrease in the complexity of \gi\@. Namely: % \begin{itemize} \item If \sga\ is polynomially enumerable, then \gi\ can be recognized in randomized polynomial time\@. % \item For \(\epsilon < {1 \over 2}\), if \sga\ is \(n^\epsilon\textrm{-enumerable}\), then \gi\ can be recognized in deterministic polynomial time\@. \end{itemize} % \apar{1-4} Currently, \gi\ does not seem to be solvable in polynomial time using either randomized or deterministic computations\@. Hence, these results could also be interpreted as results on the non-enumerability of \sga\@. % \apar{1-5} The rest of the paper is organized as follows\@. In Section~2, we provide some technical background and formal definitions for the terms used in this paper\@. In Section~3, we construct a graph gadget that allows us to combine many instances of \gi\ into one instance of \sga\@. In Sections~4 and 5, we present the results connecting the enumerability of \(\sga\) and the complexity of \gi\@. Finally, in Section~6 we give an upper bound on the enumerability of \(\sga\)\@. % \asection{2}{Preliminaries} \label{se:def} % \apar{2-1} In this paper, we will work with many complexity classes\@. We assume that the reader is familiar with \P\ and \NP, the classes of languages recognized by deterministic and nondeterministic polynomial-time Turing machines\@. We will use \PH\ to denote the Polynomial Hierarchy and \R\ to denote the class of languages recognized by probabilistic polynomial-time Turing machines with bounded one-sided error\@. We refer the reader to standard references \cite{cj99-01-04,cj99-01-05,cj99-01-29} in complexity theory for explanations on the relationships among these classes\@. % \apar{2-2} An instance of the Graph Isomorphism (GI) problem is a pair of undirected graphs \((G,H)\)\@. Without loss of generality, the vertices of the graphs are indexed \(1\) through \(n\)\@. The pair \((G,H)\) is an element of \gi\ if there exists a bijection \(f\) from the vertices of \(G\) to the vertices of \(H\) that preserves the edge relations --- i.e., \((u,v)\) is an edge in the graph \(G\) if and only if \((f(u), f(v))\) is an edge in \(H\)\@. In this case, \(f\) is called an isomorphism between \(G\) and \(H\) and we write \(G \iso H\)\@. Note that we may think of \(f\) as a permutation of the set \(\{1, \dots, n\}\)\@. Whereas GI is a set or, alternatively a decision problem, \sgi\ is a function, or a counting problem\@. The value of the function \sgi\ on input \((G,H)\) is the number of isomorphisms from \(G\) to \(H\)\@. % \apar{2-3} An instance of the Graph Automorphism (GA) problem is a single graph \(G\)\@. The graph \(G\) is an element of \ga\ if \(G\) has a non-trivial automorphism --- i.e., an isomorphism between \(G\) and itself other than the identity function\@. Analogously, the function \sga\ computes the number of automorphisms on \(G\)\@. It is often more convenient to work with GA instead of GI because the set of automorphisms of a graph forms a group under composition\@. % \apar{2-4} Clearly, the set \gi\ is an element of \NP\ because an \NP\ machine can guess a permutation and check that the permutation is indeed an isomorphism between two graphs\@. As we have mentioned before, \gi\ is known to be incomplete for \NP\ unless the Polynomial Hierarchy collapses\@. The complexities of \sgi, \ga, and \sga\ can be estimated based upon their relationship to \gi\@. For example, \ga\ reduces to \gi\ by a many-one polynomial-time reduction\@. Therefore, \ga\ is also an element of \NP\ and cannot be complete for \NP\ unless \PH\ collapses\@. Clearly, \gi\ reduces to \sgi\ because knowing the number of isomorphisms certainly tells you whether one exists\@. In addition, one can compare the complexities of these problems as oracles\@. Using the group structure of \ga, one can show that \(\P^{\gi} = \P^{\sga} = \P^{\sgi}\) \cite{cj99-01-24, cj99-01-17}, \cite[Theorem 1.24]{cj99-01-20}\@. Thus, treated as oracles for \P, the problems \gi, \sga\ and \sgi\ have essentially the same complexity\@.\footnote{Of course, \(\P^{\ga} \subseteq \P^{\sga}\), but whether \(\P^{\sga} \subseteq \P^{\ga}\) remains an open problem\@.} % \apar{2-5} The incompleteness of \gi\ also shows that \(\P^{\sgi}\) cannot contain any \(\textrm{NP-complete}\) problems unless \PH\ collapses\@. This result sets the Graph Isomorphism problem apart from the \NP-complete problems\@. For example, consider the satisfiability problem \textup{SAT} and the corresponding counting problem \sSAT, which outputs the number of satisfying assignments of a Boolean formula\@. \SAT\ is, of course, \NP-complete, so \(\P^{\SAT} = \P^{\NP}\)\@. However, \sSAT\ is \(\#\P\)-complete\footnote{A function \(f\) is in the class \(\#\P\) if there exists an \NP\ machine \(N\) such that \(f(x)\) equals the number of accepting paths in the computation of \(N(x)\)\@.}, and it also known that \(\P^{\sSAT}\) contains the entire Polynomial Hierarchy \cite{cj99-01-31}\@. Thus, the complexity of \sSAT\ is much higher than the complexity \SAT, whereas the complexity of \sgi\ is at the same level as that of \gi\@. Note that the complexity of the counting version of a problem is not necessarily a good predictor of the complexity of the decision version of the problem\@. For example, deciding whether a bipartite graph has a perfect matching can be done in polynomial time, but counting the number of perfect matchings in a bipartite graph is \(\#\P\)-complete \cite{cj99-01-32}\@. However, since the counting versions of natural \NP-complete problems are \(\#\P\)-complete, the observation that \(\P^{\gi} = \P^{\sgi}\) nevertheless suggests that \gi\ is not \NP-complete\@.\footnote{Considering the example of perfect matchings in bipartite graphs, one should not claim that the counting version of a problem being hard implies that the decision problem is hard\@. However, one might still argue that if the counting version of a problem is easy, then the decision problem might be easy\@.} This observation was interpreted by many authors as ``evidence'' that \gi\ might not be \NP-complete before the incompleteness of \gi\ was proven \cite{cj99-01-17}\@. % \apar{2-6} Returning to graph automorphisms, we note that the value of \(\sga(G)\) has several special properties\@. First, \(\sga(G)\) must range from 1 to \(n!\) because the identity function is always an automorphism and there are at most \(n!\) permutations of the \(n\) vertices\@. Second, the set of automorphisms of \(G\) forms a subgroup of \(S_{n}\), the set of all permutations of \(\{1, \dots, n\}\) under composition\@. This group structure can be exploited in many ways\@. For example, from LaGrange's Theorem, we know that \(\sga(G)\) must divide \(n!\), hence \(\sga(G)\) cannot have factors larger than \(n\)\@. Thus, given \(\sga(G)\) as input, it is possible to obtain a complete prime factorization of \(\sga(G)\) in polynomial time\@. The following observations about \sga\ and prime numbers will be needed throughout the paper\@. % \begin{alabsubtext}{Lemma}{1}{}\label{le:use} %\begin{lemma} % Let \(G\) be a graph with \(n\) vertices\@. For \(i \geq 1\), let \(m_i\) be the \(i\)th smallest prime number larger than \(n\)\@. % \begin{enumerate} \item \(\sga(G)\) divides \(n!\)\@. \item \(m_i\) does not divide \(\sga(G)\)\@. \item There exists a prime \(p\) such that\ \(m_i< p < 2m_i\)\@. \item \label{part:density} For \(n \geq 17\), \(m_i \leq 2 (n \log n + i \log i)\)\@. \item \(m_i\) can be computed in time \(n^{O(1)} + i^{O(1)}\)\@. \end{enumerate} \end{alabsubtext} %\end{lemma} % \begin{alabsubtext}{Proof of Lemma}{1}{} \prooffontshape %\begin{proof} Parts~1 and 2 follow from the preceding discussion\@. Part~3 is just Bertrand's Postulate \cite{cj99-01-16} (that there exists a prime number between \(x\) and \(2x\))\@. Part~4 can be derived easily from a result of Rosser and Schoenfeld \cite{cj99-01-27}, which states that the number of primes less than \(x\) is between \(x/\ln x\) and \(1.25506 x/\ln x\), for \(x \geq 17\)\@. (These are estimates for the constants in the Prime Number Theorem\@.) Part~5 follows from Part~4, because \(m_i\) is polynomial in \(n\) and \(i\)\@. Since we can list all the primes below a number \(x\) in time polynomial in \(x\) (not the length of \(x\)), \(m_i\) can be found in time polynomial in \(n\) and \(i\)\@. {\nopagebreakbeginpar\markendlst{Proof of Lemma 1}} \end{alabsubtext} %\end{proof} % \apar{2-7} Thus, \sga\ cannot take on every value between 1 and \(n!\) since some of these numbers cannot be the order of a subgroup of \(S_{n}\)\@. This leads us to ``enumerability'' as a measure of complexity\@. The concept of enumerability in computational complexity theory was introduced independently by Beigel \cite{cj99-01-06} and by Cai and Hemachandra \cite{cj99-01-09} then later modified by Amir, Beigel, and Gasarch \cite{cj99-01-01}\@. % \begin{alabsubtext}{Definition}{1}{}\label{de:enum} %\begin{definition} \apar{Definition 1-1} Let \(b: \nat \rightarrow \nat\) be polynomially bounded\@. A function \(f\) is \emph{\(b(n)\textrm{-enumerable}\)} if there exists a polynomial-time computable function \(g\), such that for all \(x\), \(g(x)\) outputs a list of at most \(b(|x|)\) values, one of which is \(f(x)\)\@. A function \(f\) is \emph{poly-enumerable\/} if \(f\) is \(b(n)\textrm{-enumerable}\) for some polynomial \(b\)\@. % \apar{Definition 1-2} For super-polynomial \(b:\nat \rightarrow \nat\), \(f\) is \emph{\(b(n)\textrm{-enumerable}\)\/} if there exists a polynomial-time computable function \(g\), such that for all \(x\), \(f(x)\) is one of the \(b(|x|)\) values in the sequence \(g(x,0), g(x,1), \dots, g(x, b(|x|) - 1)\)\@. (Here we assume that the second input to \(g\) is written in binary\@.) \end{alabsubtext} %\end{definition} % \apar{2-8} Intuitively, we think of the enumerability of functions as a generalization of approximability\@. For example, suppose a function \(f: \nat\rightarrow\nat\) is approximable within a factor of 2\@. Then, there is a polynomial-time computable function, which, for all \(x\), outputs a value \(y\) and guarantees that \(y \leq f(x) \leq 2y\)\@. Thus, the set of possible values of \(f(x)\) is restricted to the numbers between \(y\) and \(2y\)\@. For enumerability, the set of possible values does not have to be an interval\@. Another difference between enumerability and approximability is that in approximability the number of possible values is ``output sensitive'' --- i.e., the number of possible values of \(f(x)\) depends directly on \(f(x)\) rather than \(x\)\@. In addition, approximability is only meaningful when there is a natural total ordering on the range of the function, whereas enumerability makes sense in a broader setting\@. % \apar{2-9} The algorithm that computes \sga\ in polynomial time using a \gi\ oracle is a group-theoretic algorithm and proceeds roughly as follows (see \cite{cj99-01-17,cj99-01-20} for details)\@. Let \(A\) be the automorphism group of a graph \(G\)\@. Consider a tower of subgroups of \(A\) \[ I = A^{(n)} \leq A^{(n-1)} \leq \dots \leq A^{(1)} \leq A^{(0)} = A, \] where \(I\) is the trivial group containing only the identity permutation and \(\leq\) denotes the subgroup relation\@. Here, \(A^{(i)}\) is the subgroup of \emph{pointwise stabilizers} of \(\{1, \dots, i\}\) in \(A\) --- i.e., the set of permutations \(\psi \in A\) such that for all \(j\), with \(1 \leq j \leq i\), \(\psi(j) = j\)\@. The order of the group \(A\) can then be determined by iteratively computing the order of the subgroups \(A^{(n)}\), \(A^{(n-1)}\), \dots, \(A^{(0)}\)\@. This iterative procedure relies on the fact that a labeled isomorphism between two graphs can be constructed in polynomial time using a \gi\ oracle\@. A labeled graph isomorphism between graphs \(G\) and \(H\) with \(n\) vertices is a permutation of \(\{1, \dots, n\}\) that preserves the edge relations of \(G\) and \(H\) as well as labels assigned to vertices of \(G\) and \(H\)\@. For example, if we label both vertex \(j\) in \(G\) and vertex \(j\) in \(H\) with the label \(\ell_{j}\) for \(1 \leq j \leq i\), then we can guarantee that any labeled isomorphism between \(G\) and \(H\) is in fact a pointwise stabilizer of \(\{1, \dots, i\}\)\@. This result occurs because any labeled isomorphism is forced to map vertex \(j\) in \(G\) to vertex \(j\) in \(H\) for \(1 \leq j \leq i\)\@. The labels on the vertices of a labeled graph can be simulated in an unlabeled graph by attaching large cliques or long cycles to the vertices\@. In the example above, the label \(\ell_{j}\) assigned to vertex \(j\) can be simulated in an unlabeled graph by attaching a cycle of \(n+j\) new vertices to vertex \(j\) by using a single edge\@. Again, any isomorphism between \(G\) and \(H\) must map vertex \(j\) in \(G\) to vertex \(j\) in \(H\) for \(1 \leq j \leq i\)\@. Note that if the original graphs \(G\) and \(H\) are planar, then the simulated labeled graphs are also planar\@. Since planar graph isomorphism can be computed in polynomial time \cite{cj99-01-18,cj99-01-19}, this procedure also computes \(\sga(G)\) for planar graphs in polynomial time\@. Similarly, the simulated labeling scheme applied to bounded genus graphs does not change the genus of the graph\@. Thus, \(\sga(G)\) can also be computed in polynomial time for bounded genus graphs\@. Attaching a long cycle to a vertex in a bounded-degree graph will increase the degree of the vertex by 1\@. So, \(\sga(G)\) is again polynomial-time computable for bounded degree graphs\@. Thus, in each of these special cases, \(\sga(G)\) is in fact 1-enumerable\@.\footnote{It is not clear to the authors how this labeling scheme would affect graphs with bounded eigenvalue multiplicity\@.} % \apar{2-10} There do exist functions that cannot be polynomially enumerated unless some intractibility assumptions are violated\@. For example, Cai and Hemachandra showed that unless \(\P = \PP\), the function \sSAT\ is not \(n^\epsilon\textrm{-enumerable}\) for \(\epsilon < 1\)\@.\footnote{\PP\ is the class of languages recognized by probabilistic polynomial-time Turing machines with unbounded two-sided error\@. Since PP contains \NP, the conclusion \(\P = \PP\) is generally considered to be unlikely\@.} This result was improved independently by Cai and Hemachandra \cite{cj99-01-10} and by Amir, Beigel, and Gasarch \cite{cj99-01-01}, who showed that \(\P = {\rm PP}\) if and only if \sSAT\ is \(p(n)\textrm{-enumerable}\) for some polynomial \(p\)\@. Moreover, Amir, Beigel, and Gasarch \cite{cj99-01-01} proved that unless the Polynomial Hierarchy collapses to its fourth level, \sSAT\ is not \(2^{n^\epsilon}\textrm{-enumerable}\) for \(\epsilon < 1\)\@. Since \sSAT\ is clearly \(2^n\textrm{-enumerable}\), these results show tight upper and lower bounds on the enumerability of \sSAT, if we assume that \PH\ does not collapse\@. % \apar{2-11} In the present paper, we investigate the enumerability of \(\sga\)\@. Our motivation for studying the enumerability of \(\sga\) is twofold\@. First, the results mentioned above, combined with Toda's theorem that every set in \PH\ reduces to \sSAT\ \cite{cj99-01-31}, show that \(\sga\) cannot be \(\#\P\)-complete unless PH collapses to \(\P^{\NP}\) (actually to \(\P^{\gi}\))\@. Therefore, the enumerability properties of \(\sga\) might be very different from those of \sSAT\@. Also, connections between the enumerability of \(\sga\) and the complexity of \gi\ might help us obtain a better classification of the Graph Isomorphism problem\@. % \apar{2-12} Throughout the paper, we use the number of vertices in a graph as the measure of the size of the input\@. We do this to simplify the terminology even though the length of the encoding of a graph could be as long as \(n^{2}\)\@. In certain cases, this convention does have an effect on our results\@. For example, Theorem~1 is stated for \(\epsilon < 1/2\); without this convention, the statement would be \(\epsilon< 1/4\)\@. % \asection{3}{Combining Lemma} \label{se:comb} % \apar{3-1} In this section we show how to combine many instances of \(\gi\) into one instance of \(\sga\)\@. This lemma will be used in the proofs of the main theorems of Sections~4 and 5\@. First, we need to define the notion of reductions between two functions (as opposed to sets)\@. % \begin{alabsubtext}{Definition}{2}{}\label{de:red} \upshape{(Krentel \cite{cj99-01-21})}~ Let \(f\) and \(g\) be two functions\@. We say that \(f\) reduces to \(g\), written \(f \pml g\), if there exist two polynomial-time computable functions \(S\) and \(T\) such that \[ f(x) = S(x,g(T(x))). \] \end{alabsubtext} % \apar{3-2} Intuitively, \(f \pml g\) implies that \(f\) is easier than \(g\), because \(g\) provides enough information for a polynomial-time function to compute \(f\)\@. These reductions are also called \emph{metric reductions} in the literature\@. % \apar{3-3} To simplify our notation, we will also use the following notational device for generalized characteristic functions\@. For a set \(A\) and an ordered list \(x_{1}, \dots, x_{r}\) of instances of \(A\), the function \(\Char{A}(x_{1}, \dots, x_{r})\) outputs a sequence of \(r\) bits such that the \(i\)th bit is 1 if and only if \(x_{i} \in A\)\@. Note that \(r\) does not have to be constant here\@. % \apar{3-4} Now, we are ready to prove the Combining Lemma\@. This key lemma allows us to construct a graph \(\eF\) from \(q\) instances of the Graph Isomorphism problem, \GHq, such that \(\sga(\eF)\) provides enough information to determine in polynomial time whether \(G_i\) is isomorphic to \(H_i\) for each instance \((G_i, H_i)\)\@. % \begin{alabsubtext}{Lemma}{2}{Combining Lemma}\label{le:key} %\begin{lemma} There exist polynomial-time functions \(T\) and \(S\) such that \(\CharGI \pml \sga\) via \(T\) and \(S\)\@. Furthermore, in the case where the ordered list \(\Qlist = \ang{\GHq}\) consists of pairs of graphs with \(n\) vertices, the following hold for the graph \(\eF\) output by \(T(\Qlist)\)\@. % \begin{enumerate} \item The \(\eF\) has \(O(n^{2} q \log n + n q^2 \log q)\) vertices\@. \item The output of \(S(\Qlist,\sga(\eF))\) can be computed from \((n,q,\sga(\eF))\)\@. \end{enumerate} \end{alabsubtext} %\end{lemma} % \begin{alabsubtext}{Proof of Lemma}{2}{} \prooffontshape %\begin{proof} \apar{Proof of Lemma 2-1} In the construction below, the running time of \(T\) will be polynomial in \(|\Qlist|\), which is polynomial in \(n+q\)\@. This allows for the possibility that \Qlist\ has many small graphs\@. In the first step of the construction, we find \(m_1, \dots, m_{q}\), the \(q\) prime numbers immediately following the number \(n\)\@. Let \(r_i = (m_i + 1)/2\)\@. Assuming that each graph in \(\Qlist\) has at least 2 vertices, \(r_i\) is an integer\@. For each \(i\), \(1 \leq i \leq q\), we construct a graph \(C_i\) as follows\@. Take \(r_i\) copies of \(G_i\), \(r_i\) copies of \(H_i\), and a complete graph with \(2 r_i\) new vertices \(a_1,\dots,a_{2 r_i}\)\@. Connect each vertex in the \(j\)th copy of \(G_i\) to \(a_j\)\@. Connect each vertex in the \(j\)th copy of \(H_i\) to \(a_{r_i + j}\)\@. (See Figure~1\@.) Call the resulting graph \(C_i\)\@. % \begin{figure} \framebox[\columnwidth][l]{ \begin{minipage}{\columnwidth} % \begin{center} \setlength{\unitlength}{0.0125in} \begin{picture}(250,228)(0,-10) \put(83,63){\blacken\ellipse{4}{4}} \put(83,63){\ellipse{4}{4}} \put(70,81){\blacken\ellipse{4}{4}} \put(70,81){\ellipse{4}{4}} \path(90,22)(102,50) \path(61,41)(83,63) \path(42,70)(70,81) \put(70,128){\blacken\ellipse{4}{4}} \put(70,128){\ellipse{4}{4}} \put(83,147){\blacken\ellipse{4}{4}} \put(83,147){\ellipse{4}{4}} \put(101,160){\blacken\ellipse{4}{4}} \put(101,160){\ellipse{4}{4}} \path(42,140)(70,128) \path(61,169)(83,147) \path(90,188)(101,160) \put(180,82){\blacken\ellipse{4}{4}} \put(180,82){\ellipse{4}{4}} \put(167,63){\blacken\ellipse{4}{4}} \put(167,63){\ellipse{4}{4}} \put(149,50){\blacken\ellipse{4}{4}} \put(149,50){\ellipse{4}{4}} \path(208,70)(180,82) \path(189,41)(167,63) \path(160,22)(149,50) \put(148,160){\blacken\ellipse{4}{4}} \put(148,160){\ellipse{4}{4}} \put(167,147){\blacken\ellipse{4}{4}} \put(167,147){\ellipse{4}{4}} \put(180,129){\blacken\ellipse{4}{4}} \put(180,129){\ellipse{4}{4}} \path(160,188)(148,160) \path(189,169)(167,147) \path(208,140)(180,129) \put(65,105){\blacken\ellipse{4}{4}} \put(65,105){\ellipse{4}{4}} \put(125,165){\blacken\ellipse{4}{4}} \put(125,165){\ellipse{4}{4}} \put(125,45){\blacken\ellipse{4}{4}} \put(125,45){\ellipse{4}{4}} \put(185,105){\blacken\ellipse{4}{4}} \put(185,105){\ellipse{4}{4}} \put(125,105){\ellipse{120}{120}} \path(65,105)(35,105) \path(185,105)(215,105) \path(125,195)(125,165) \path(125,45)(125,15) \put(102,50){\blacken\ellipse{4}{4}} \put(102,50){\ellipse{4}{4}} \put(55,170){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\mytwlrm \(G _i\)}}}}} \put(195,170){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \(H_i\)}}}}} \put(35,140){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\mytwlrm \(G_i\)}}}}} \put(60,35){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\mytwlrm \(G_i\)}}}}} \put(30,100){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\mytwlrm \(G_i\)}}}}} \put(220,100){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \(H_i\)}}}}} \put(190,35){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \(H_i\)}}}}} \put(40,60){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\mytwlrm \(G_i\)}}}}} \put(210,60){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \(H_i\)}}}}} \put(155,10){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \(H_i\)}}}}} \put(95,10){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\mytwlrm \(G_i\)}}}}} \put(95,195){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\mytwlrm \(G_i\)}}}}} \put(155,195){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \(H_i\)}}}}} \put(125,200){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\mytwlrm \(G _i\)}}}}} \put(125,0){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\mytwlrm \(H_i\)}}}}} \put(86,66){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(89,63){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(83,70){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(158,144){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(161,141){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(164,137){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(72,120){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(74,124){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(76,128){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(124,52){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\myninrm \(a_ {r_i+1}\)}}}}} \put(95,56){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\myninrm \(a_{r_i}\)}}}}} \put(81,137){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\myninrm \(a_3\)}}}}} \put(98,150){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\myninrm \(a_2\)}}}}} \put(125,155){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\myninrm \(a _1\)}}}}} \put(148,56){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(144,53){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(140,51){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \@.}}}}} \put(154,153){\makebox(0,0)[rb]{\raisebox{0pt}[0pt][0pt]{\shortstack[r]{{\myninrm \(a_{2r_i}\)}}}}} \put(215,140){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\shortstack[l]{{\mytwlrm \(H_i\)}}}}} \end{picture} \end{center} \end{minipage} } % \afigcap{1}{Combining \(r_i\) copies of \(G_i\) and \(H_i\)} \label{fig:combine} \end{figure} % \apar{Proof of Lemma 2-2} Now, suppose that \(G_i\) is isomorphic to \(H_i\)\@. Then every automorphism of \(C_i\) can be formed by a permutation of the vertices in \(\{a_1,\dots,a_{2 r_i}\}\) followed by an automorphism of each copy of \(G_i\) and \(H_i\)\@. Hence \[ \sga(C_i)=(2 r_i)!(\sga(G_i))^{2r_i}. \] Since \(2 r_i = m_i + 1\), the prime number \(m_i\) divides \(\sga(C_i)\)\@. % \apar{Proof of Lemma 2-3} On the other hand, if \(G_i\) is \emph{not} isomorphic to \(H_i\), then every automorphism of \(C_i\) can be formed by a permutation of the vertices in \(\{a_1,\dots,a_{r_i}\}\), followed by a permutation of the vertices in \(\{a_{r_i+1},\dots,a_{2r_i}\}\) and the automorphisms of each copy of \(G_i\) and \(H_i\)\@. In this case, \[ \sga(C_i)=(r_i)!(r_i)!(\sga(G_i))^{r_i}(\sga(H_i))^{r_i}. \] Since \(r_i < m_i\) and \(|G_i| = |H_i| = n < m_i\), the prime number \(m_i\) does not divide \(\sga(C_i)\)\@. In summary, \begin{equation} \label{eqn:is-iso} G_i \iso H_i \iff m_i {\rm ~divides~} \sga(C_i). \end{equation} % \apar{Proof of Lemma 2-4} Let \eF\ be the disjoint union of all the \(C_i\), for \(1 \leq i \leq q\)\@. The output of the function \(T(\Qlist)\) will be \eF\@. Since each \(C_i\) has \((m_i + 1)(n + 1)\) vertices, the total number of vertices in \eF\ is \[ (n + 1) \sum_{i = 1}^{q} (m_i + 1) < q (n + 1) ( m_{q} + 1 ). \] By Lemma~1 part~4, we know that \(m_{q} \leq 2 (n \log n + q\log q)\)\@. Hence, we can bound the number of vertices in \eF\ by \(O(n^2 q \log n + n q^{2} \log q)\)\@. % \apar{Proof of Lemma 2-5} Now, we show how \(\sga(\eF)\) can be used to compute \(\CharGI(\Qlist)\)\@. By the construction of \eF, \begin{equation} \sga(\eF) = \prod_{i=1}^{q} \sga(C_i). \label{eqn:combined} \end{equation} We also know that for all \(i\), \(1 \leq i \leq q\), \[ G_i \iso H_i \implies m_i {\rm ~divides~} \sga(\eF). \] However, the converse may not hold because \(\sga(C_j)\) for some \(j > i\) may contain \(m_i\) as a factor\@. Thus, to determine whether \(G_i \iso H_i\) from \(\sga(\eF)\), these extraneous \(m_i\) factors (if they exist) must be removed\@. To do this, we start with the last \(C_i\), namely \(C_{q}\)\@. Since \(m_j < m_{q}\) for all \(j < q\), we know that \[ G_{q} \iso H_{q} \iff m_{q} {\rm ~divides~} \sga(\eF). \] Now, if \(G_{q} \iso H_{q}\), then \(C_{q}\) contributes an \((m_{q} + 1)!\) factor to \(\sga(\eF)\); otherwise, \(C_q\) contributes an \((r_i)!(r_i)!\) factor to \(\sga(\eF)\)\@. % \apar{Proof of Lemma 2-6} To determine whether \(G_{q-1} \iso H_{q-1}\) we need to remove the prime factors greater than \(n\) from \(\sga(\eF)\) that came from \(\sga(C_{q})\)\@. Since \(\sga(G_{q})\) and \(\sga(H_{q})\) do not contain prime factors greater than \(n\), the prime factors \(> n\) in \(\sga(C_{q})\) come from either \((m_{q}+1)!\) or \((r_{q})!(r_{q})!\) depending on whether \(G_{q} \iso H_{q}\) (which we have already determined)\@. So, let \[ N_i = \left \{ \begin{array}{@{}ll} \sga(\eF) & \textrm{if~} i = q \\[2ex] \displaystyle \frac{N_{i+1}}{(m_{i+1} + 1)!} & \mbox{if \(m_{i+1}\) divides~} N_{i+1} \\[3ex] \displaystyle \frac{N_{i+1}}{(r_{i+1})!(r_{i+1})!} & \textrm{otherwise} \\[2ex] \end{array} \right . \] From the preceding discussion, it is clear that \(G_i \iso H_i \iff m_i\) divides \(N_i\)\@. Thus, the function \(S\) can compute \(\CharGI(\GHq)\) from \(\sga(\eF)\), \(n\) and \(q\), by finding \(m_1, m_2, \dots, m_{q}\) and calculating \(N_1, N_2, \dots, N_{q}\)\@. {\nopagebreakbeginpar\markendlst{Proof of Lemma 2}} \end{alabsubtext} %\end{proof} \asection{4}{\#GA and \(n^{\epsilon}\)-enumerability} \label{se:enum} % \apar{4-1} The main theorem in this section shows that it is unlikely for \sga\ to be \(n^{\epsilon}\textrm{-enumerable}\) because, for any \(\epsilon < 1/2\), \sga\ is \(n^{\epsilon}\textrm{-enumerable}\) if and only if \(\gi\) can be recognized in polynomial time\@. We begin with a review of two constructions from the literature\@. The first one shows that the Graph Isomorphism problem is ``self-computable'' in the sense that, given \gi\ as an oracle, we can construct an isomorphism between two isomorphic graphs in polynomial time \cite{cj99-01-20,cj99-01-28}\@. We reproduce the proof of this well-known theorem because we need to make references to the construction in the proof and because we need to estimate the sizes of the graphs queried\@. % \begin{alabsubtext}{Lemma}{3}{} \label{lemma:self} %\begin{lemma} There exists a polynomial-time Turing machine using \gi\ as an oracle which finds an isomorphism between two graphs, if the graphs are isomorphic\@. \end{alabsubtext} %\end{lemma} % \begin{alabsubtext}{Proof of Lemma}{3}{} \prooffontshape %\begin{proof} \apar{Proof of Lemma 3-1} We prove that \gi\ is ``self-computable'' by constructing a mapping between the vertices of two isomorphic graphs \(G\) and \(H\) and using \gi\ as an oracle\@. This ``self-computable'' property is similar to the disjunctive self-reducibility of \SAT\@.\footnotemark\ In the first stage of the construction, we find a vertex \(i_1\) in \(H\) such that there is an isomorphism between \(G\) and \(H\) mapping vertex 1 in \(G\) to vertex \(i_1\) in \(H\)\@. This is accomplished by trying all \(n\) vertices in \(H\) exhaustively and asking the \gi\ oracle the \(n\) questions: \footnotetext{That is, given any Boolean formula \(F\), consider the formula \(F_{0}\) obtained by replacing the first variable of \(F\) with the Boolean value FALSE and the formula \(F_{1}\) obtained by replacing the first variable with TRUE\@. Then, \(F \in \SAT\) if and only if \(F_{0} \in \SAT\) or \(F_{1} \in \SAT\) (see \cite[Section~4.5]{cj99-01-04} and \cite[Section~4.5]{cj99-01-29})\@.} % \apar{Proof of Lemma 3-2} \begin{quote} Is there an isomorphism from \(G\) to \(H\) mapping vertex 1 to vertex \(i_1\)? \end{quote} Such questions can be transformed into queries to \gi\ by attaching cycles with \(n+1\) vertices to vertex \(1\) in \(G\) and vertex \(i_1\) in \(H\)\@. Thus, any isomorphism between the transformed graphs must map vertex 1 in \(G\) to vertex \(i_1\) in \(H\)\@. If such an isomorphism exists, the remaining \(n-1\) stages of the construction assign vertices \(2, \dots, n\) in \(G\) to the vertices in \(H\) under the restriction that vertex 1 maps to vertex \(i_1\)\@. In stage \(k\) of the construction, vertex \(k\) in \(G\) and \(i_k\) in \(H\) will be attached to a cycle with \(n+k\) vertices\@. {\nopagebreakbeginpar\markendlst{Proof of Lemma 3}} \end{alabsubtext} %\end{proof} % \begin{alabsubtext}{Remark}{1}{} %\begin{remark} It is convenient to think of the procedure described in the preceding proof as a \emph{self-reduction tree}\@. The root of the tree, level \(0\), is labeled with the graphs \((G,H)\)\@. Each vertex at level \(k\) has \(n-k\) children that represent the \(n-k\) possible assignments of vertex \(k\) in \(G\) to the \(n-k\) remaining vertices in \(H\)\@. These vertices are labeled with the corresponding transformed graphs\@. This tree has \(n!\) leaves, so we cannot construct the entire tree in polynomial time\@. However, at the leaves of the tree, every vertex of \(G\) is assigned to some vertex of \(H\)\@. Thus, in polynomial time we can determine whether the mapping represented by a leaf is indeed an isomorphism between \(G\) and \(H\)\@. \end{alabsubtext} %\end{remark} % \apar{4-2} In the proof of Theorem~1 below, our strategy is to traverse the \mbox{self-reduction} tree from the top down\@. Since the tree has exponentially many paths, we will need to identify some of the paths as dead-ends\@. The following combinatorial lemmas \cite{cj99-01-08,cj99-01-26} will help us prune the tree and maintain a polynomial bound on the running time of the tree traversal\@. % \begin{alabsubtext}{Definition}{3}{} %\begin{definition} For a collection \(\C\) of sets and a set \(X\), we say \(X\) \emph{separates} \(C\) if for all \(S,S'\in \C\), \(S \ne S' \implies S \cap X \ne S' \cap X\)\@. \end{alabsubtext} %\end{definition} % \begin{alabsubtext}{Lemma}{4}{}\label{lemma:combinatorial} %\begin{lemma} For a collection \(\C\) of sets, with \(|\C| = n \ge 1\), there exists a set \(X\) that separates \(\C\), where \(|X| \le n-1\)\@. \end{alabsubtext} %\end{lemma} % \apar{4-3} The lemma below adapts Lemma~4 to show that if we have \(\ell\) vectors in \(\{0,1\}^{\ell}\), then the vectors can be uniquely identified by their values at \(\ell - 1\) coordinates\@. Thus, one of the coordinates is not needed to distinguish the vectors from each other\@. In the following, we use \((\bvec)_{i}\) to denote the \(i\)th component of a vector \(\bvec \in \Sigma^{\ell}\)\@. % \begin{alabsubtext}{Lemma}{5}{}\label{lemma:useful} %\begin{lemma} Let \(m \leq \ell\) and \(\bvec_1, \dots, \bvec_m \in \{0,1\}^{\ell}\)\@. There exists a coordinate \(k\) such that for all \(\bvec_{i} \neq \bvec_{j}\), there exists \(t \neq k\) such that \((\bvec_i)_t \neq (\bvec_j)_t\)\@. Moreover, \(k\) can be found in time polynomial in \(\ell\)\@. \end{alabsubtext} %\end{lemma} % \begin{alabsubtext}{Proof of Lemma}{5}{} \prooffontshape %\begin{proof} It suffices to prove the case where \(m = \ell\)\@. Use Lemma~4 where \(\C\) is the collection of subsets of \(\{1,\dots,\ell\}\) represented by the bit vectors \(\bvec_{1},\dots,\bvec_{\ell}\)\@. Let \(k\) be an element not contained in the separator \(X\)\@. Since \(X\) is a separator, each pair of bit vectors must differ at coordinates other than \(k\)\@. The coordinate \(k\) can be found in time polynomial in \(\ell\) because we can simply try all possible values for \(k\) and check each pair of \(\bvec_{i}\) and \(\bvec_{j}\)\@. This takes time \(O(\ell^{4})\)\@. {\nopagebreakbeginpar\markendlst{Proof of Lemma 5}} \end{alabsubtext} %\end{proof} % \apar{4-4} We are now ready to prove the main result of this section\@. The techniques used in this proof and in Lemma~5 are derived from results on enumerability and self-reducibility by Amir, Beigel, and Gasarch \cite{cj99-01-01}\@. % \begin{alabsubtext}{Theorem}{1}{}\label{th:nep} %\begin{theorem} For \(\epsilon < 1/2\), the function \(\sga\) is \(n^\epsilon\textrm{-enumerable}\) if and only if \(\gi\in\P\)\@.\footnotemark \end{alabsubtext} %\end{theorem} % \apar{4-5} \footnotetext{Recall that the \(n\) in ``\(n^{\epsilon}\textrm{-enumerable}\)'' is the number of vertices in the graph\@. If \(n\) is the length of the encoding of the graph, we would need to further restrict \(\epsilon < 1/4\)\@.} % \begin{alabsubtext}{Proof of Theorem}{1}{} \prooffontshape %\begin{proof} \apar{Proof of Theorem 1-1} In Section~2, we outlined a polynomial-time algorithm for \sga\ that uses \gi\ as an oracle\@. Thus, if \(\gi \in \P\), then \sga\ is also computable in polynomial time\@. In this case, \sga\ would be 1-enumerable\@. Thus, we only need to show that, if \(\sga\) is \(n^{\epsilon}\textrm{-enumerable}\), then \(\gi \in \P\)\@. % \apar{Proof of Theorem 1-2} Given two graphs \(G\) and \(H\) with \(n\) vertices, we search the self-reduction tree described above in stages\@. We maintain a list \Qlist\ of pairs of graphs from the self-reduction tree\@. Initially, \Qlist\ contains just the pair \((G,H)\)\@. Throughout the tree-pruning procedure we maintain the invariant that \(G \iso H\) if and only if \Qlist\ contains a pair of isomorphic graphs (i.e., \(\CharGI(\Qlist)\) is not all zeroes)\@. Also, the size of the list \(\Qlist\) will always be polynomially bounded\@. In the beginning of every stage of the tree pruning, we take each pair of graphs in \Qlist\ and replace it with its children in the self-reduction tree\@. We continue the replacement until \Qlist\ has at least \(q(n)\) pairs (for \(q(n) \geq n\) to be determined below)\@. % \apar{Proof of Theorem 1-3} Let \(\Qlist' = \ang{(G_{1}, H_{1}), \dots, (G_{q(n)}, H_{q(n)})}\) be the first \(q(n)\) pairs in \Qlist\@. Let \(m\) be an upper bound on the size of these graphs\@. We apply the Combining Lemma to construct the graph \eF\ that has at most \(r = m q(n)^{2} \log q(n)\) vertices\@. Then, we use the enumerator for \(\sga\) on \eF\ to obtain a list of \(r^{\epsilon}\) numbers, one of which is \(\sga(\eF)\)\@. The function \(S\) in the Combining Lemma converts these numbers into a list of \(r^{\epsilon}\) vectors \(\bvec_{1},\dots,\bvec_{r^{\epsilon}}\) in \(\{0,1\}^{q(n)}\), one of which is \(\CharGI(\Qlist')\)\@. Now, suppose that \(\bvec_i \neq 0^{q(n)}\) for all \(i\), \(1 \leq i \leq r^\epsilon\)\@. Then, we know that \(\CharGI(\Qlist') \neq 0^{q(n)}\), so \(G\) must be isomorphic to \(H\)\@. Thus, we can halt the pruning procedure and accept\@. In the remaining case, we may assume that \(0^{q(n)}\) is one of the vectors in \(\bvec_{1},\dots,\bvec_{r^\epsilon}\)\@. We will pick \(q(n)\) below so that \(r^{\epsilon} \leq q(n)\)\@. Then, Lemma~5 gives us a coordinate \(k\) such that for \(\bvec_i \neq \bvec_{j}\), the vectors \(\bvec_{i}\) and \(\bvec_{j}\) differ on a coordinate other than \(k\)\@. Now, it cannot be the case that \((G_k,H_k)\) is the only isomorphic pair of graphs in \(\Qlist'\) because, in that case, \(\CharGI(\Qlist') = 0^{k-1}10^{q(n)-k}\); hence, \(\CharGI(\Qlist')\) can only be distinguished from \(0^{q(n)}\) using the \(k\)th coordinate\@. Thus, the pruning process can safely remove the pair \((G_k, H_k)\) from the list \Qlist\ and still guarantee that if \Qlist\ contains an isomorphic pair before pruning, then it also does after pruning\@. % \apar{Proof of Theorem 1-4} We continue removing items from \Qlist\ until it has fewer than \(q(n)\) pairs of graphs\@. Then we proceed to the next stage\@. After at most \(n\) stages, the pairs in \Qlist\ are leaves of the self-reduction tree, so we can compute \(\CharGI(\Qlist)\) in polynomial time\@. By the invariant we have maintained, \(G \iso H\) if and only if \(\CharGI(\Qlist)\) is not all zeroes\@. Thus, we have shown that \(\gi \in \P\)\@. % \apar{Proof of Theorem 1-5} Finally, we need to show that by picking \(q(n)\) to be \(n^{\alpha}\) where \(\alpha > 1/(1-2\epsilon)\), we can guarantee that \(r^{\epsilon} \leq q(n)\)\@. (The constant \(\alpha\) is positive since \(\epsilon < 1/2\)\@.) {}From the construction of the self-reduction tree in Lemma~3, we know that \(m\) is \(O(n^{2})\) since the graphs \(G_{i}\) and \(H_{i}\) consist of \(n\) original vertices and cycles of size \(n+1\) through \(2n\)\@. So, \[ r^{\epsilon} \leq (c n^{2} \cdot q(n)^{2} \cdot \log q(n))^{\epsilon} = (cn^{2} \cdot n^{2\alpha} \cdot \alpha \log n)^{\epsilon}. \] Thus, \(r^{\epsilon} < n^{2\epsilon + 2\alpha\epsilon + \delta}\) for all \(\delta > 0\)\@. From our choice of \(\alpha\), we know that \[ 2\epsilon + 2\alpha\epsilon < 1 + 2 \alpha\epsilon < \alpha. \] Therefore, \(r^{\epsilon} \leq q(n)\)\@. {\nopagebreakbeginpar\markendlst{Proof of Theorem 1}} \end{alabsubtext} %\end{proof} % \apar{4-6} Since it is generally believed that \(\gi \not\in \P\), the preceding theorem can also be interpreted as a lower bound on the enumerability of \sga\@. We can also use the theorem to obtain a lower bound on the bounded query complexity of \sga\@. The bounded query classes are defined as follows\@. % \begin{alabsubtext}{Definition}{4}{}\label{de:bdq} %\begin{definition} Let \(j(n)\) be a function and \(X\) be a set\@. A function \(f\) is in \(\PFq{j(n)}{X}\) if there exists a polynomial-time oracle Turing machine that computes \(f\) using no more than \(j(n)\) queries to \(X\) on inputs of length \(n\)\@. \end{alabsubtext} %\end{definition} % \apar{4-7} Counting the number of oracle queries has been established as a useful complexity measure\@. For example, the number of queries to an \NP\ oracle can be used to characterize the complexity of approximating \NP-optimization problems \cite{cj99-01-12,cj99-01-13}\@. The following fact shows that there is an intimate connection between the enumerability of a function and the bounded query complexity of that function\@. % \begin{alabsubtext}{Fact}{1}{}\label{fa:bdq} %\begin{fact} {\rm \cite[Lemma 3.2]{cj99-01-07}} Let \(f\) be any function and \(j(n)\) be a polynomial-time computable function\@. The following are equivalent: \begin{enumerate} \item There exists \(X\) such that \(f\in \PFq{j(n)}{X}\)\@. \item \(f\) is \(2^{j(n)}\textrm{-enumerable}\)\@. \end{enumerate} \end{alabsubtext} %\end{fact} % \apar{4-8} Using Fact~1 we can obtain a lower bound on the number of queries needed to compute \sga, assuming that \(\gi \not\in \P\)\@. % \begin{alabsubtext}{Corollary}{1}{} %\begin{corollary} Let \(\epsilon < 1/2\)\@. If there exists an \(X\) such that \(\sga\in \PFq {\epsilon\log n} X\), then \(\gi\in\P\)\@. \end{alabsubtext} % \asection{5}{\#GA and poly-enumerability} \label{se:poly} % \apar{5-1} Assuming that \(\gi \not\in \P\), the main result in the previous section is a ``non-enumerability'' result\@. In general, we would like to prove stronger non-enumerability results for \sga\@. For example, Amir, Beigel, and Gasarch \cite{cj99-01-01} were able to prove that \sSAT\ is not \(2^{n^{\epsilon}}\textrm{-enumerable}\) for \(\epsilon < 1\) unless the Polynomial Hierarchy collapses\@. We cannot use their machinery for the case of \sga\ because it turns out that \sga\ is actually \(\exp(O(\sqrt{n \log n}))\textrm{-enumerable}\)\@. Instead, we adapt the techniques of Goldwasser, Micali, and Rackoff \cite{cj99-01-15} to show that \(\sga\) cannot be poly-enumerable unless \(\gi \in \R\)\@.\footnote{We were motivated in part by Lozano and Tor\'an\ \cite[Theorem~5.1]{cj99-01-22}, who also used this technique in their proof\@.} % \apar{5-2} Goldwasser, Micali, and Rackoff showed that Graph Non-Isomorphism, the complement of \gi, can be recognized by a two-round interactive protocol\@. We briefly review this protocol in order to motivate the proof of Theorem~2\@. There are two parties involved in the interactive protocol: an all-powerful prover and a randomized polynomial-time verifier\@. The verifier asks the prover to convince him that the input graphs \((G, H)\) are \emph{not} isomorphic as follows\@. In secret, the verifier randomly picks one of \(G\) and \(H\) along with a random permutation \(\psi\)\@. He applies \(\psi\) to either \(G\) or \(H\), whichever one he picked, and obtains a new graph \(X\)\@. Then, the verifier asks the prover whether \(X\) is a permuted version of \(G\) or of \(H\)\@. If \(G\) and \(H\) are not isomorphic, the all-powerful prover simply checks if \(G \iso X\) or if \(H \iso X\) and provides the appropriate answer\@. On the other hand, if \(G\) and \(H\) are isomorphic, \(X\) can be a permuted version of either graph\@. In that case, the prover can only provide the correct answer with probability one-half\@. Thus, if \(G \not\iso H\), there exists a prover who can always convince the verifier to accept\@. Conversely, if \(G \iso H\), no prover (even one that ``lies'') can convince the verifier to accept with greater than 50 percent probability\@. % \apar{5-3} In the proof below, our randomized algorithm for \gi\ will play the role of the verifier, and the enumerator for \sga\ will play the role of the prover\@. However, unlike the prover in an interactive protocol, the enumerator provides several answers at once\@.\footnote{Another difference is that the enumerator cannot ``lie'' in the same manner as the prover because one of the answers it provides must be the correct value of \sga\@.} Thus, it is possible for the enumerator to give two answers at the same time: one that corresponds to \(G \iso H\) and one to \(G \not\iso H\)\@. We cope with this situation by emulating the interactive protocol many times in parallel\@. Thus, instead of picking one permutation \(\psi\) and forming one permuted graph \(X\), we pick \(q(n)\) permutations \(\psi_{1}, \dots, \psi_{q(n)}\) and form \(q(n)\) graphs \(X_{1}, \dots, X_{q(n)}\), each of which is a permutation of either \(G\) or \(H\)\@. % \begin{alabsubtext}{Notation}{1}{} %\begin{notation} For each permutation \(\psi \in S_n\), we use \(\psi(G)\) to denote the graph obtained by re-labeling the vertices of \(G\) using \(\psi\)\@. Given two permutations \(\psi, \rho \in S_{n}\), we define \(\psi\thinspace\compose \rho \in S_{n}\) to be the functional composition of \(\psi\) and \(\rho\) --- i.e., \((\psi\thinspace\compose \rho) (G) = \psi ( \rho (G) )\)\@. \end{alabsubtext} %\end{notation} % \newcommand{\riso}{\mbox{R-ISO}} % \begin{alabsubtext}{Theorem}{2}{}\label{th:poly} %\begin{theorem} If \(\sga\) is poly-enumerable, then \(\gi\in\R\)\@. \end{alabsubtext} %\end{theorem} % \begin{alabsubtext}{Proof of Theorem}{2}{} \prooffontshape %\begin{proof} \apar{Proof of Theorem 2-1} Assuming that \(\sga\) is \(p(n)\textrm{-enumerable}\) via an enumeration function \(g\), we will construct a randomized polynomial-time algorithm to decide whether the input graphs \(G\) and \(H\) are isomorphic\@. Let \(n\) be the number of vertices in \(G\) and \(H\) and let \(q(n) \geq n\) be a polynomial to be specified later\@. As discussed above, we randomly pick \(q(n)\) permutations \(\psi_{1}, \dots, \psi_{q(n)}\) from \(S_{n}\) and, for each \(\psi_{i}\), permute either \(G\) or \(H\)\@. Our choice of applying \(\psi_{i}\) to either \(G\) or \(H\) can be represented by a single bit\@. So, a bit vector \(\bvec \in \bitq\) and the permutations \(\psi_{1}, \dots, \psi_{q(n)}\) fully specify our random choices\@. Let \(b_{i}\) be the \(i\)th bit of \(\bvec\) and \(X_{i}\) be the result of applying the permutation \(\psi_{i}\); that is, \[ X_i = \left\{ \begin{array}{ll} \psi_i(H) & {\rm if~} b_i = 0 \\[\jot] \psi_i(G) & {\rm if~} b_i = 1. \end{array} \right . \] % \apar{Proof of Theorem 2-2} Now, consider the instances of the graph isomorphism problem: \(\GXqn\)\@. Note that, if \(G\) \emph{is not\/} isomorphic to \(H\), then \[ \CharGI(\GXqn) = \bvec, \] since \(G\) is isomorphic to \(X_{i}\) only when \(X_{i} = \psi_{i}(G)\)\@. On the other hand, if \(G\) \emph{is\/} isomorphic to \(H\), then our choice of applying \(\psi_{i}\) to \(G\) or \(H\) does not change whether \(G\) is isomorphic to \(X_{i}\)\@. So, in this case, \[ \CharGI(\GXqn) = 1^{q(n)}. \] % \apar{Proof of Theorem 2-3} Next, we use the Combining Lemma on \(\GXqn\) to construct a graph \(\eF\) such that \(\sga(\eF)\) provides enough information to compute \(\CharGI(\GXqn)\)\@. Let \(r(n)\) be a polynomial upper bound on the number of vertices in \(\eF\)\@. If we could compute \(\sga(\eF)\) directly, then we could immediately determine whether \(G \iso H\) by checking whether \(\sga(\eF)\) corresponds to the case where \(\CharGI(\GXqn)\) is \(\bvec\) or \(1^{q(n)}\)\@.\footnote{The exception is the pathological case where we chose \(\bvec = 1^{q(n)}\)\@. However, this case only occurs with probability \(1/2^{q(n)}\)\@.} However, we cannot compute \(\sga(\eF)\) directly, so we use the enumerator for \(\sga(\eF)\) instead\@. Let \(T\) and \(S\) be the reduction functions from the Combining Lemma\@. (We used \(T\) on \(\GXqn\) to obtain the graph \(\eF\)\@.) Since we assume that \(\sga\) is \(p(n)\textrm{-enumerable}\), in polynomial time we can compute \(g(\eF)\), a set of polynomially many values, one of which is \(\sga(\eF)\)\@. For each value in \(g(\eF)\), we use the \(S\) function from the Combining Lemma to determine a possible value for \(\CharGI(\GXqn)\)\@. Call the set of all such values \[ \POSS = \{~ S(n,q(n),N) ~|~ N \in g(\eF) ~\}. \] If \(G \not\iso H\), then \(\bvec = \CharGI(\GXqn)\)\@. Thus, \(\bvec\) must be an element of \(\POSS\) since \(\CharGI(\GXqn)\) is always an element of \POSS\@. On the other hand, if \(G \iso H\), then \(\bvec \in \POSS\) occurs with very low probability\@. (This will be proven below\@.) Therefore, the strategy for our randomized algorithm is to accept \((G,H)\) if and only if \(\bvec \not\in \POSS\)\@. Figure~2 summarizes Procedure~\riso, the randomized algorithm to determine whether \(G \iso H\)\@. % \begin{figure} % \framebox[\columnwidth][l]{ \begin{minipage}{\columnwidth} \noindent Procedure \riso\((G,H)\) \begin{enumerate} \item Randomly pick \(\bvec\in\bitq\) and \(\psi_{1}, \dots, \psi_{q(n)}\in S_{n}\)\@. \item Use the Combining Lemma to construct \[{\cal F} = T(\GXqn).\] \item Use \(g\) to generate the possible values of \(\sga(\cal F)\)\@. \item Compute the set \(\POSS = \{S(n,q(n),N) ~|~ N\in g(\eF)\}\)\@. \item If \(\bvec \not\in \POSS\) then output YES, otherwise output NO\@. \end{enumerate} \end{minipage} } % \afigcap{2}{Randomized procedure to determine whether the graphs \(G\) and \(H\) are isomorphic\@.} \label{fig:riso} \end{figure} % \apar{Proof of Theorem 2-4} If \(G \not\iso H\), then Procedure~\riso\ outputs NO with probability 1\@. We need to show that, if \(G \iso H\), then Procedure~\riso\ outputs YES with high probability\@. Intuitively, it is unlikely for \(\bvec \in \POSS\) when \mbox{\(G\iso H\)} because \POSS\ is completely determined by \(\eF\) and the same \(\eF\) can be the result of exponentially many random choices\@. We prove this formally by showing that for each of choice of \(\bvec\) and \(\psi_{1}, \dots, \psi_{q(n)}\) made by Procedure~\riso, there is a block of \(2^{q(n)}\) random choices that produces the same graph \(\eF\)\@. Each random choice within a block has a distinct \(\bvec\)\@. Thus, within each block, the probability that \(\bvec \in \POSS\) is at most \(p(r(n))/2^{q(n)}\)\@. Furthermore, we will show that the blocks form a partition of the set of all random choices made by Procedure~\riso\@. Thus, the overall probability that \(\bvec \in \POSS\) is also bounded by \(p(r(n))/2^{q(n)}\)\@. % \apar{Proof of Theorem 2-5} The blocks are defined as follows\@. Assume that \(G\) is isomorphic to \(H\)\@. Since permutations are invertible, for every graph \(Y\) isomorphic to \(G\), there exists a permutation \(\rho\) such that \(\rho(H) = Y\)\@. Now, fix a sequence of permutations \(\sigma_{1}, \dots, \sigma_{q(n)} \in S_{n}\) and let \(Y_{i} = \sigma_{i}(G)\)\@. Let \(\rho_{1}, \dots, \rho_{q(n)}\) be the corresponding permutations such that \(\rho_{i}(H) = Y_{i}\)\@. Let \(\bvec\) be any bit vector chosen by Procedure~\riso\@. Then, there exists a choice of \(\psi_{1}, \dots, \psi_{q(n)}\) such that the graph \(X_{i}\) constructed in Procedure~\riso\ is exactly \(Y_{i}\), namely: \[ \psi_{i} = \left\{ \begin{array}{ll} \rho_{i} & {\rm if~} b_i = 0 \\[\jot] \sigma_{i} & {\rm if~} b_i = 1. \end{array} \right . \] Furthermore, if we fix an isomorphism \(\tau\) from \(H\) to \(G\), the permutation \(\psi_{i}\) is completely determined by \(b_{i}\) and \(\sigma_{i}\) --- i.e., \(\psi_{i} = \sigma_{i}\ \compose\ \tau\) if \(b_{i} = 0\) and \(\psi_{i} = \sigma_{i}\) if \(b_{i} = 1\)\@. Thus, we can associate the permutations \(\sigma_{1}, \dots, \sigma_{q(n)}\) with a block of \(2^{q(n)}\) random choices for Procedure~\riso\ (since there are \(2^{q(n)}\) different bit vectors \(\bvec\))\@. To see that every choice of \(\bvec\) and \(\psi_{1}, \dots, \psi_{q(n)}\) corresponds to some block, simply note that we can set \(\sigma_{i} = \psi_{i}\thinspace\compose\ \tau^{-1}\) if \(b_{i} = 0\) and \(\sigma_{i} = \psi_{i}\) if \(b_{i} = 1\)\@. This will again guarantee that \(Y_{i} = X_{i}\) for every \(i\)\@. Therefore, the blocks do form a partition of the set of all random choices made by Procedure~\riso\@. % \apar{Proof of Theorem 2-6} Finally, observe that for each of the \(2^{q(n)}\) distinct bit vectors \(\bvec\) in a block, the same instances of GI, \(\GXqn\), are constructed by Procedure~\riso\@. Thus, the same set \POSS\ is generated\@. Since \POSS\ has \(p(r(n))\) elements and since \(p(r(n))\) is polynomially bounded, the probability that a randomly chosen \(\bvec\) is not an element of \POSS\ is at least \(1 - {p(r(n))\over2^{q(n)}}\)\@. Thus, for \(q(n)\) large enough, Procedure~\riso\ will accept with high probability in the case that \(G \iso H\)\@. {\nopagebreakbeginpar\markendlst{Proof of Theorem 2}} \end{alabsubtext} %\end{proof} % \apar{5-4} As before, we can translate the non-enumerability of \sga\ into lower bounds on its bounded query complexity using Fact~1\@. % \begin{alabsubtext}{Corollary}{2}{} %\begin{corollary} If there exists an \(X\) such that \(\sga\in \PFq {O(\log n)} X\), then \(\gi\in\R\)\@. \end{alabsubtext} %\end{corollary} % \asection{6}{Subexponential enumeration} \label{se:upper} % \apar{6-1} The results of the preceding section can be interpreted as lower bounds on the enumerability of \sga\ since it seems unlikely that \(\gi \in \P\) or \(\gi \in {\rm R}\)\@. In this section we provide an upper bound on the enumerability of \sga\ by showing that \(\sga\) is \(\exp(O(\sqrt{n\log n}))\textrm{-enumerable}\)\@. Our enumerator will be oblivious\@. That is, given a graph \(G\) with \(n\) vertices and an index \(\ell\), the output of this enumerator \(g(G,\ell)\) will depend only on \(n\) and \(\ell\)\@. We think of \(\ell\) as being an encoding of the order of a permutation group \(A\) of degree \(n\)\@. We must show that an appropriate encoding exists such that \(\ell\) takes space \(O(\sqrt{n\log n})\) and the function \(\ell \mapsto |A|\) is computable in polynomial time\@. % \begin{alabsubtext}{Definition}{5}{} \label{defn:permutation} %\begin{definition} Let \(S_{n}\) be the group of all permutations of \(\Omega = \{1, \dots, n\}\) under composition\@. A subgroup \(A\) of \(S_{n}\), written \(A \leq S_{n}\), is also called a permutation group of degree \(n\) and \(\Omega\) is called the permutation domain of \(A\)\@. The order of the subgroup \(A\), written \(|A|\), is the number of permutations in \(A\)\@. \end{alabsubtext} %\end{definition} % \begin{alabsubtext}{Lemma}{6}{}\label{le:Q} %\begin{lemma} Let \(A\) be a subgroup of \(S_n\)\@. Let \(p_i\) be the \(i\)th prime\@. Then \(|A|\) must be of the form \(\prod_{i=1}^m p_i^{d_i}\) where \begin{enumerate} \item for all \(i\), \(d_i\le n\)\@. \item \(m \le n/ \ln n + o(n/\ln n)\)\@. \end{enumerate} \end{alabsubtext} %\end{lemma} % \begin{alabsubtext}{Proof of Lemma}{6}{} \prooffontshape %\begin{proof} Let \(m\) and \(d_1,\dots,d_m\) be such that \(|A|=\prod_{i=1}^m p_i^{d_i}\)\@. Since \(|A|\) is a divisor of \(n!\), we know that for all \(i\), \(p_i^{d_i}\) divides \(n!\)\@. However, for any prime \(p\), the highest power of \(p\) dividing \(n!\) is \(p^d\), where \[ d = \sum_{j\geq 1} \left\lfloor \frac{n}{p^j} \right\rfloor < n\sum_{j\geq 1}\frac{1}{p^j} = \frac{n}{p-1}\leq n. \] (This formula simply counts the number of positive integers up to \(n\) that are divisible by \(p\), \(p^2\), and so on\@.) In particular, all the prime factors of \(|A|\) are \(\le n\)\@. The Prime Number Theorem states that \[ \displaystyle \lim_{n \rightarrow \infty} \frac{\pi(n)}{n/\ln n} = 1, \] where \(\pi(n)\) is the number of primes less than or equal to \(n\)\@. Thus, \(m \leq n / \ln n + o(n/\ln n)\)\@. {\nopagebreakbeginpar\markendlst{Proof of Lemma 6}} \end{alabsubtext} %\end{proof} % \begin{alabsubtext}{Theorem}{3}{}\label{th:upper} %\begin{theorem} \(\sga\) is \(\exp(O(\sqrt{n\log n}))\textrm{-enumerable}\) via an oblivious enumerator\@. \end{alabsubtext} %\end{theorem} % \begin{alabsubtext}{Proof of Theorem}{3}{} \prooffontshape %\begin{proof} Let \(G\) be a graph\@. The set of automorphisms of \(G\) is a subgroup of \(S_n\); hence, \(\sga(G)\) must be of the form specified in Lemma~6\@. We show how to enumerate all possible sizes of the subgroups of \(S_n\)\@. We describe this in the form of a compressed encoding of orders of subgroups of \(S_n\), such that the encoding lengths are \(O(\sqrt{n\log n})\) and, given the encoding of \(|A|\), we can compute \(|A|\) in polynomial time\@. One method would be to simply write down the binary representations of the \(d_i\), for \(1\leq i\leq\pi(n)\)\@. By Lemma~6, the number of bits used would be \(O(n)\), which is too many\@. However, we will use this technique for ``small'' primes\@. % \apar{6-2} Let \(k=\sqrt{n\log n}\)\@. Then \(\pi(k)=O(k/\log n)=O(\sqrt{n/\log n})\)\@. For \(A\leq S_n\), the first part of the encoding of \(A\) will consist of the binary representations of the \(d_i\) for \(p_i\leq k\)\@. This encoding uses \(O(\pi(k)\log n) =O(\sqrt{n\log n})\) bits, as desired\@. To encode the exponents of the larger primes, we must use detailed knowledge of the possible orders of subgroups of \(S_n\)\@. However, our task will be greatly simplified by the fact that we can now ignore the small primes\@. % \apar{6-3} Let \(\Omega\) denote \(\{1,\dots,n\}\)\@. For \(x\in\Omega\), \(x^A\) denotes \emph{the \(A\)-orbit of \(x\)} defined by: \[ x^{A} = \{~ y \in \Omega ~|~ (\exists\ \psi \in A)[y = \psi(x)] ~\}. \] We say that an orbit is \emph{trivial\/} if it has one element, and we say that \(A\) is \emph{transitive\/} if \(\Omega\) is an orbit\@. In any case, the \(A\)-orbits partition \(\Omega\)\@. We describe two divide-and-conquer techniques based on this partition\@. Let \(\Delta=x^A\) be an \(A\)-orbit, and let \(A_x\) denote the subgroup \(\{~ \psi \in A ~|~ \psi(x) = x ~\}\) of those permutations that fix \(x\)\@. It is well known that \[ |A|=|A_x|\cdot|\Delta|, \] so if \(|\Delta|\) has only prime factors \(\leq k\), we may replace \(A\) by \(A_x\) for the purposes of the second part of the encoding\@. We henceforth assume that all nontrivial orbits of \(A\) have orders divisible by some prime larger than \(k\) (so, in particular, there are at most \(\sqrt{n/\log n}\) nontrivial orbits)\@. Actually, we make the more general assumption that, for any proper subgroup \(B\) of \(A\), the index \(|A|/|B|\) is divisible by a prime larger than \(k\)\@. % \apar{6-4} Now suppose that \(|\Delta|=m\), and let \(B\) be the subgroup of \(S_m\) obtained from \(A\) by ignoring the action outside of \(\Delta\)\@. That is, \(B\) consists of those permutations \(\psi \in S_{m}\) for which there exist \(\psi' \in A\) such that \(\psi'\) is an extension of \(\psi\)\@. Let \(A_{\Delta}\) denote the subgroup of \(A\) that fixes every point of \(\Delta\) (i.e., \(A\) is the subgroup of pointwise stabilizers of \(\Delta\) in \(A\))\@. Then \(|A|=|B|\cdot|A_\Delta|\), and to encode \(|A|\) it suffices to first encode \(|B|\) and then recursively encode \(|A_\Delta|\)\@. The number of orbits \(\Delta\) that need to be considered is \(O(\sqrt{n/\log n})\), so we must use no more than \(O(\log n)\) bits to encode \(|B|\)\@. To do this, we make great use of the fact that \(B\) is transitive\@. % \apar{6-5} Now suppose that \(\Delta_1,\dots,\Delta_r\) is a partition of \(\Delta\) with \(1 k\)\@. Let \(N\) be the subgroup of \(B\) that fixes the blocks, i.e., any \(x\in N\) sends each \(\Delta_i\) to itself\@. Let \(K\) be the subgroup of \(S_r\) obtained from \(B\) by considering the action on the blocks\@. Then \(|B|=|N|\cdot|K|\)\@. In addition, every orbit of \(N\) has order less than \(k\), so \(|N|\) is a product of primes whose values are at most \(k\)\@. Thus, to encode \(|B|\), it suffices to encode \(|K|\)\@. By minimality of \(r\), \(K\) is \emph{primitive\/}, i.e., preserves no nontrivial partition of the permutation domain\@. % \apar{6-6} Much is already known about the structure of primitive groups\@. The O'Nan--Scott Lemma \cite[Theorem 4.1]{cj99-01-11} classifies them into several types\@. Many of these are ruled out by our assumption that the index of any proper subgroup of \(K\) is divisible by some prime larger than \(k\) (where \(k^2\) is bigger than \(r\), the size of the permutation domain)\@. In fact, it must be the case that \(K\) has a simple normal subgroup \(T\)\@. Further, either \(|T|=r\) and \(K\) is a subgroup of the automorphism group of \(T\times T\), or \(K\) is a subgroup of the automorphism group of \(T\)\@. Following the Classification of Finite Simple groups, much is known about the permutation representations of finite simple groups \cite{cj99-01-03}\@. In particular, either \(T\) is one of polynomially many alternating or classical groups (each of which can be described by a string of length \(O(\log n)\)), or \(|K|\) is polynomially bounded\@. In the first case \(|K|/|T|\) is polynomially bounded, so in either case \(O(\log n)\) bits suffice to describe the order of \(K\)\@. % \apar{6-7} We summarize the encoding of \(|A|\)\@. First, we write down the binary representations of the exponents of the primes in \(|A|\) for all primes \(p\leq k\)\@. Then, we write down a sequence of \(O(n/k)\) pairs \((\langle T \rangle,N)\), where \(\langle T \rangle\) is an \(O(\log n)\)-length name of a group \(T\) that is either the trivial group or a classical group with a permutation representation of degree \(\leq n\) and \(N\) is a positive integer (written in binary) that is at most \(n^c\) for some constant \(c\)\@. For primes \(p>k\), the \(p\)-part of \(|A|\) is the product of the \(p\)-parts of the \(N\)'s and the orders of the \(T\)'s\@. The order of \(T\) is given by an explicit formula, so \(|A|\) can be computed in polynomial time from its encoding\@. The first part of the encoding uses \(O(\pi(k)\log n)\) bits; the second part of the encoding uses \(O((n/k)\log n)\) bits\@. Both of these quantities are \(O(\sqrt{n\log n})\) as desired\@. {\nopagebreakbeginpar\markendlst{Proof of Theorem 3}} \end{alabsubtext} %\end{proof} % \asection{7}{Discussion} % \apar{7-1} Several open problems remain on the enumerability of \(\sga\)\@. We have shown that if \(\sga\) is poly-enumerable, then \(\gi \in \R\)\@. For \SAT, we know that if \(\sSAT\) poly-enumerable, then \(\P= {\rm PP}\) \cite{cj99-01-01,cj99-01-10}, which implies that \(\SAT \in \P\)\@. For \(\sga\), it remains open whether \(\sga\) being poly-enumerable could imply that \(\gi \in \P\)\@. It might even be possible to show that, if \(\sga\) is \(2^{n^\epsilon}\textrm{-enumerable}\) for some \(\epsilon<1/2\), then \(\gi \in \P\)\@. Such a theorem would not violate our upper bound that \(\sga\) is \(\exp(O(\sqrt{n\log n}))\textrm{-enumerable}\)\@. Note that an analogous result for \(\sSAT\), that \(\sSAT\) is \(2^{n^{\epsilon}}\)-enumerable implies \(\SAT \in \P\), is not known\@. % \apar{7-2} While no polynomial-time algorithms for \gi\ or \sga\ have been discovered, algorithms with subexponential running time do exist\@. For example, there exists an algorithm with time complexity \(\exp(O(\sqrt{n\log n}))\) that computes the automorphism group and its generators \cite{cj99-01-03} (this is harder than solving \gi\ and \sga)\@. This algorithm combines the techniques of several authors including Babai, Luks, and Zemlyachenko\@. The bound on the running time is the same as the upper bound on the enumerability of \sga\ that we achieved in Section~6\@. This striking observation brings up the possibility of the following time-enumeration trade-off\@. By allowing the enumerator to run for longer than polynomial time, for example, time \(\exp(O((n\log n)^a +\log n))\), it might be possible to achieve \(\exp(O((n\log n)^b))\)-enumerability for \(a+b=1/2\)\@. Note that the case \(a=1/2\) is given by the subexponential-time algorithm mentioned above \cite{cj99-01-03}, and the case \(a=0\) is our upper bound\@. The case \(0