SYLOW THEOREM IN POLYNOMIAL-TIME

Given a set GAMMA of permutations of an n-set, let G be the group of permutations generated by GAMMA . If p is a prime, a Sylow p-subgroup of G is a subgroup whose order is the largest power of p dividing (G). For more than 100 years it has been known that a Sylow p-subgroup exists, and that for any two Sylow p-subgroups P//1, P//2 of G there is an element g an element of G such that P//2 equals g** minus **1P//1g. We present polynomial-time algorithms that find (generators for) a Sylow p-subgroup of G, and that find g an element of G such that P//2 equals g** minus **1P//1g whenever (generators for) two Sylow p-subgroups P//1, P//2 are given. These algorithms involve the classification of all finite simple groups.