% 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