MINIMUM PERMUTATION GROUP BASE

• INSTANCE: Permutation group on n letters.

• SOLUTION: A base for G, i.e., a sequence of points $b_1, \ldots, b_k$ such that the only element in G fixing all of the $b_i$ is the identity.

• MEASURE: The size of the base, i.e., k.

  
  

• Good News: Approximable within $\log\log n$ [82].