[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