The complexity of the weight problem for permutation and matrix groups. (Q960944): Difference between revisions

Given a metric \(d\) on a permutation group \(G\), the weight of an element of \(G\) is defined as its distance from the identity element. The paper under review is mainly concerned with three problems: the weight problem, the maximum weight problem and the minimum weight problem. These problems are to decide whether there exists an element in \(G\) such that its weight equals \(k\), is greater than or equal to \(k\), is less than or equal to \(k\), respectively, for some given value \(k\) in the range of \(d\). The main results are that for many well-known metrics such as the Hamming distance, the Cayley distance and \(l_\infty\) all of these problems are \(\mathbf{NP}\)-complete with the exception of the maximum weight problem for \(l_\infty\) which is in \(\mathbf P\). In the proofs, the problems are reduced to problems in coding theory which are known to be \(\mathbf{NP}\)-complete. A similar problem in matrix groups, the eigenvalue-free problem, is also investigated in this paper.