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

DOI10.1016/j.disc.2009.03.005zbMath1211.20002OpenAlexW2011640602MaRDI QIDQ960944

Taoyang Wu, Peter J. Cameron

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

permutation groupsNP-complete problemsmetricssubgroup distancesweight problems

Mathematics Subject Classification ID

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

Related Items (2)

Testing permutation properties through subpermutations ⋮ Finding fixed point free elements and small bases in permutation groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the subgroup distance problem.
• Linear optimization over permutation groups
• On permutation groups with bounded movement
• On the number of fixed point free elements in a permutation group
• The complexity of the Weight Problem for permutation groups
• On the inherent intractability of certain coding problems (Corresp.)
• Derangements and Eigenvalue-Free Elements in Finite Classical Groups
• The intractability of computing the minimum distance of a code
• On a theorem of Jordan

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