The complexity of the Weight Problem for permutation groups

Peter J. Cameron*, Taoyang Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element g ∈ G such that d(g, e) = k for some k ∈ N. In this paper we show that this problem is NP-complete for many well known metrics.

Original languageEnglish
Pages (from-to)109-116
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume28
DOIs
Publication statusPublished - 1 Mar 2007

Keywords

  • Metrics
  • NP-complete
  • Permutation Group
  • Weight Problem

Fingerprint

Dive into the research topics of 'The complexity of the Weight Problem for permutation groups'. Together they form a unique fingerprint.

Cite this