Permutation Groups and the Graph Isomorphism Problem - Perspectives in Computational Complexity - page 188

in the coset G α x 1 as this coset is precisely the set of elements of Gx that maps α
to β . A similar algorithm can be given for left cosets xG as well. We thus have the
following lemma:

Lemma 5.2 Computing the lexicographically least element in a coset can be done
in polynomial-time.

The above lemma is a key step in proving that the graph isomorphism problem is
in the complexity class SPP.

Definition 5.3 ( SPP ) For a non-deterministic polynomial-time Turing machine let
gap denote the difference in the number of accepting paths and rejecting paths

of M on the input x . A language L is in the complexity class SPP if there is a
polynomial time non-deterministic Turing machine M such that for all strings x in
the language L ,thegap

( M , x )

( M , x ) is 1 and for all strings not in the language L ,gap ( M , x )

is 0.

Languages in SPP are believed to be of low complexity and are unlikely to be
NP-hard. In particular, any gap definable complexity [ FFK91 ] class not only contain
SPP but also derive no extra computational power with a language in SPP as oracle,
i.e. SPP is low for all these complexity classes. Gap definable complexity classes
[ FFK91 ] are counting classes defined using GapP functions, i.e. functions that are
differences of accepting and rejecting paths of an NP machine, and contain many
common counting complexity class like PP and

≥

P, etc.
The main idea involved in the proof is to design a polynomial-time algorithm A
that makes queries to an NP language L with some restriction on the queries that
A makes to L . We design a non-deterministic polynomial-time machine M for L
such that for all queries the algorithm A makes, the machine M has at most one
accepting path. Such an oracle machine can be converted to an SPP algorithm, i.e. an
NP machine whose gap function is the characteristic function of GI, using standard
techniques [ KST92 ].
The base algorithm A is an inductive algorithm that builds the strong generating
set of the automorphism group by computing the group G i of all automorphisms that
fix the first i vertices of the graph. To compute G i − 1 from G i , the algorithm has to
query the NP-language L which essentially checks, given a j i , whether there is

an automorphism that maps i to j . The base polynomial-time machine can then find
one such by doing a prefix search. However, we need to design an NP machine M
for L such that for all queries asked by A , there is at most one accepting path. This
we achieve as follows: The algorithm A also provides to L the generator set of G i ,
i.e. queries to L are (encoding of) pairs

>

where S is a generating set of G i at
the i -th stage. We know that if there is an automorphism, say g in G i − 1 , that maps
i to j then the set of all such automorphisms form the coset G i g . The machine M
essentially guess the automorphism g that maps i to j if it exists and accepts only
if g is the lexicographically least permutation in G i g . Since there is only one such
guess g , we know that for all queries that the algorithm A makes to L the machine
M has at most one accepting path. The SPP result then follows as mentioned above.

S , j ∅