The complexity of the weight problem for permutation and matrix groups.

DOI10.1016/J.DISC.2009.03.005MaRDI QIDQ960944zbMATH OpenOpenAlexFDO

Authors Peter J. Cameron, Taoyang Wu

Publication date 29 March 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2009.03.005

zbMATH Keywords

metricsNP-complete problemspermutation groupssubgroup distancesweight problems

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Subgroups of symmetric groups (20B35) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• The complexity of the Weight Problem for permutation groups
• Algorithmic Problems for Metrics on Permutation Groups
• On the subgroup distance problem.
• The distance of a permutation from a subgroup of S_n.
• Linear optimization over permutation groups

Cites work

• Derangements and Eigenvalue-Free Elements in Finite Classical Groups
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3715700 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• Linear optimization over permutation groups
• Metrics on permutations, a survey
• On a theorem of Jordan
• On permutation groups with bounded movement
• On the inherent intractability of certain coding problems (Corresp.)
• On the number of fixed point free elements in a permutation group
• On the subgroup distance problem.
• The complexity of the Weight Problem for permutation groups
• The distance of a permutation from a subgroup of S_n.
• The intractability of computing the minimum distance of a code

Cited in

(7)

• On the subgroup distance problem.
• Finding fixed point free elements and small bases in permutation groups
• The distance of a permutation from a subgroup of S_n.
• The complexity of the Weight Problem for permutation groups
• Algorithmic Problems for Metrics on Permutation Groups
• Testing permutation properties through subpermutations
• Finding cycle types in permutation groups with few generators

This page was built for publication: The complexity of the weight problem for permutation and matrix groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q960944)