Given generators for a permutation group G on n letters, the question has been posed as to whether or not a natural polynomial time Greedy Algorithm could be used to find a minimum base for G. We show that the Greedy Algorithm does not always find a minimum base for G. In fact, the minimum base problem is NP-hard, and the corresponding decision problem, "does there exist a base for G of size no more than L?", is NP-complete.

Let G be a permutation group of degree n, and let M(G) denote the size of a minimum base for G. Then the Greedy Algorithm produces a base of size O(M(G) log log n), and this bound is sharp with respect to worst case performance. The maximum size of a nonredundant base for G is bounded above by O(M(G) log n). This, too, is optimal in the sense that there exist an infinite number of permutation groups that realize this upper bound.