Class Description

GA: Graph Automorphism

Can be defined as the class of problems polynomial-time Turing reducible to the Graph Automorphism problem.

Contains P and is contained in GI.

See [KST93] for much more information about GA.

Linked From

#GA: Graph Automorphism

The class of problems (Karp-)reducible to counting the number of automorphisms of a graph.

Counterpart of GA.

More about...


GI: Graph Isomorphism

Can be defined as the class of problems polynomial-time Turing reducible to the Graph Isomorphism problem.

Contains GA and is contained in Δ2P.

The Graph Isomorphism problem itself (as opposed to the set of problems Turing reducible to Graph Isomorphism) is contained in NP as well as coAM (and indeed SZK). So in particular, if Graph Isomorphism is NP-complete, then PH collapses.

Many natural problems are GI-complete (polynomial-time Turing equivalent to GI); for a partial list see the Wikipedia page. While many of these are GI for a restricted class of graphs, some surprising GI-complete problems are: isomorphism of finite automata, isomorphism of commutative class 3 nilpotent semigroups, isomorphism of algebras over a field whose radical squares to zero and whose radical quotient is abelian [Gri83], and isomorphism of context-free grammars (for all of these and further references see [ZKT85]). Conjugacy of semisimple Lie algebras given by matrices is also GI-hard, and is even GI-complete assuming one can compute relevant eigenvalues [Gro12].

See [KST93] for much more information about GI.

More about...