The complexity of the weight problem for permutation and matrix groups.
type: Item
instance of: scholarly article
title: The complexity of the weight problem for permutation and matrix groups.
zbMATH Open document ID: 1211.20002
author: Peter J. Cameron
author: Taoyang Wu
published in: Discrete Mathematics
publication date: 2010-03-29T00:00:00Z
review text: 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.
reviewed by: Thomas Michael Keller
Mathematics Subject Classification ID: 20B35
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5687572
zbMATH Keywords: weight problems
zbMATH Keywords: metrics
zbMATH Keywords: permutation groups
zbMATH Keywords: NP-complete problems
zbMATH Keywords: subgroup distances
MaRDI profile type: Publication
full work available at URL: j.disc.2009.03.005
OpenAlex ID: W2011640602
cites work: On the inherent intractability of certain coding problems (Corresp.)
cites work: On the subgroup distance problem.
cites work: Linear optimization over permutation groups
cites work: Q4231664
cites work: On the number of fixed point free elements in a permutation group
cites work: The complexity of the Weight Problem for permutation groups
cites work: Q3020034
cites work: Q3995195
cites work: Q3905382
cites work: Derangements and Eigenvalue-Free Elements in Finite Classical Groups
cites work: Q3221403
cites work: Q3077170
cites work: On permutation groups with bounded movement
cites work: Q4787523
cites work: On a theorem of Jordan
cites work: The intractability of computing the minimum distance of a code
cites work: Q3140234
DOI: 10.1016/J.DISC.2009.03.005
description: scientific article; zbMATH DE number 5687572