← All Problems
Open

Sylow Subgroups (SylowSub)

Category: Local Optimality

Input

A group $G$.

Problem

Find the Sylow subgroups of $G$.

Definitions

See [1].

Status

Open (Babai, Seres, and Luks [1]).

Remarks

The problem is known to be in $\P$ (Kantor [2]), however, the $\NC$ question is open even for solvable groups [1]. For a permutation group $G$, testing membership in $G$, finding the order of $G$, finding the center of $G$, and finding a composition series of $G$ are all known to be in $\NC$ [1]. Babai, Seres, and Luks present several other open questions involving group theory [1].

References

  1. L. Babai, S. Seres, and E. M. Luks. Permutation groups in NC (1987). Permutation groups in NC.
  2. W. M. Kantor (1985). Sylow’s theorem in polynomial time.
  3. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.5.8.