The minimum generating set problem

Let G be a finite group. In order to determine the smallest cardinality d(G) of a generating set of G and a generating set with this cardinality, one should repeat ‘many times’ the test whether a subset of G of ‘small’ cardinality generates G. We prove that if a chief series of G is known, then the numbers of these ‘generating tests’ can be drastically reduced. At most |G|^13/5 subsets must be tested. This implies that the minimum generating set problem for a finite group G can be solved in polynomial time.