Houjun Liu

Graph Isomorphism is in NP

Recall the definition of graph : if you can relabel \(G\) to get \(G’\), that they are the same up to relabling.

\begin{equation} \text{GISO} = \qty {\langle G,G’ \rangle \mid G \cong G’} \end{equation}

Because the prover can just give the relabeling.