The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups

Cayley's theorem says that every finite group G can be viewed as a subgroup of a symmetric group Sm for some integer m. The minimal faithful permutation degree µ(G) of a finite group G is the smallest integer m such that there is an injective homomorphism φ from G to Sm. The main result of this paper is a randomized polynomial time algorithm for computing the minimal faithful permutation degree of semisimple permutation groups. Semisimple groups are groups without any abelian normal subgroups. Apart from this, we show that: 1. For any primitive permutation group G, µ(G) can be computed in quasi-polynomial time. 2. Given a permutation group G and an integer k, the problem of deciding if µ(G) ≤ k is in NP. 3. For a group G given by its Cayley table, µ(G) can be computed in DSPACE(log3 |G|).