The complexity of the weight problem for permutation and matrix groups

Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element π∈G such that d(π,e)=k, for some given value k. 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.