Background. Mazorchuk and I were interested in computing the minimum faithful degree of a linear representation of a finite semigroup over the complex feld in this paper. One particular aspect we considered was algorithmic. The algorithm we present is as follows:
The existensial theory of $\mathbb C$ is known to lie between NP and PSPACE and if GRH is true the upper bound is closer to NP.
I don't have any idea of another approach for semigroups, but for groups one has the following alternative approach.
So one can compute all dimensions and kernels of multiplicity-free reps to find a winner. I have no idea on the complexity of computing the character table or of the remainder of the algorithm given the table.
(a) Which of the above algorithms for computing the minimum faithful degree of a group is more efficient?
(b) What is the time complexity of computing the minimum faithful degree of a finite group?
Let us assume that groups are given by their multiplication table.