Class Description

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.

Linked From

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.

More about...


TI: Tensor Isomorphism

The class of problems that are polynomial-time Turing reducible to Tensor Isomorphism. Defined in [GQ19]. Can depend on the field, and the relationship for TI over different fields is an open question, but many reductions hold for TI over any field (over finite fields or the rationals this can be done in the usual model of Turing machines; over arbitrary fields one can use the BSS model to formalize this).

Over any field F, contains GI. As with Graph Isomorphism, the Tensor Isomorphism problem itself (say, over finite fields) is contained in NP as well as coAM (and indeed SZK; the same results hold over arbitrary fields in the BSS model). So in particular, if Tensor Isomorphism is NP-complete, then PH collapses.

Many natural problems are TI-complete, such as isomorphism of d-tensors for any fixed d ≥ 3, isomorphism of algebras, conjugacy of spaces of matrices, (pseudo-)isometry of alternating matrix spaces, isomorphism of matrix p-groups of class 2 and exponent p, and equivalence of cubic forms [GQ19]. This was extended to include p-groups of class c<p and exponent p [GQ21]. Analogous classes were also defined under other group actions such as unitary, orthogonal, and symplectic groups [CGQ+24].

More about...