Membership test-based black-box group algorithm for normality testing
|Problem being solved||normality testing problem: test whether a given subgroup of a given group is normal|
|Input format|| A finite group with an encoding, a subgroup of specified by a membership test|
Assume it is possible to enumerate all elements of
|Output format|| Yes/No depending on whether is normal in |
Optionally, if the subgroup is not normal, elements such that .
|Running time||(Time taken for enumeration of all group elements)+ (Time taken to do membership test on all group elements) + ( (Time for group operations))|
Idea and outline
The idea is to first use the black-box group algorithm for small generating set-finding problem to separately compute small generating sets for . Note that for , we can enumerate all elements by first enumerating all elements of and then filtering the set using the membership test for .
Once we have small generating sets for both, we can use the generating set-cum-membership test-based black-box group algorithm for normality testing. Note that the actual normality testing takes negligible time compared to the time spent computing the generating sets.