Public View
Suggest
Download this page (.md) Download entire wiki (.zip)
Clone entire wiki

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} = \left\{\langle G,G’ \rangle \mid G \cong G’\right\} \end{equation}

Because the prover can just give the relabeling.

Page updated