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