[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/graph_isomorphism_is_in_np.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Graph Isomorphism is in NP" type: concept source: https://www.jemoka.com/posts/kbhgraph_isomorphism_is_in_np/ confidence: high status: active --- 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.