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 S<inf>m</inf> 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 S<inf>m</inf>. 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(log³ |G|).