The complexity of the weight problem for permutation and matrix groups

Given a metric dd on a permutation group GG, the corresponding weight problem is to decide whether there exists an element π∈Gπ∈G such that d(π,e)=kd(π,e)=k, for some given value kk. Here we show that this problem is NP-complete for many well-known metrics. An analogous problem in matrix groups, eigenvalue-free problem, and two related problems in permutation groups, the maximum and minimum weight problems, are also investigated in this paper.