[Solved]: Group isomorphism to graph ismorphism

Problem Detail: In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For example, on the stated page it says that graph isomorphism is a more general problem than group isomorphism. Hence I am posing the following

Given a group $G$ can someone give a construction of a graph $Gamma(G)$ of size polynomial in $|G|$ such that $$Gamma(G) cong Gamma(H) iff G cong H$$ for groups $G$ and $H?$

Asked By : Jernej

Answered By : Yuval Filmus

The reduction is described in a classic paper of Miller.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35764  Ask a Question  Download Related Notes/Documents

Leave a Reply