Definition
Graph Isomorphism Problem
The graph isomorphism problem is the decision problem of determining whether two finite graphs have the same structure up to a relabelling of their vertices.
Instance: two finite graphs
and . Question: does there exist a bijection
such that, for every , Equivalently, the question is whether
under a graph isomorphism. The corresponding language is